Learning Equivalence Classes of Bayesian Network Structures with GFlowNet
Authors: Michelle Liu
Zhaocheng Zhu
Olexa Bilaniuk
Emmanuel Bengio
Venue: Accepted by TMLR ()

Abstract: Understanding the causal graph underlying a system is essential for enabling causal inference, particularly in fields such as medicine and genetics. Identifying a causal Directed Acyclic Graph (DAG) from observational data alone is challenging because multiple DAGs can encode the same set of conditional independencies. These equivalent DAGs form a Markov Equivalence Class (MEC), which is represented by a Completed Partially Directed Acyclic Graph (CPDAG). Effectively approximating the CPDAG is crucial because it facilitates narrowing down the set of possible causal graphs underlying the data. We introduce CPDAG-GFN, a novel approach that uses a Generative Flow Network (GFlowNet) to learn a posterior distribution over CPDAGs. From this distribution, we sample high-reward CPDAG candidates that approximate the ground truth, with rewards determined by a score function that quantifies how well each graph fits the data. Additionally, CPDAG-GFN incorporates a sparsity-preferring filter to enhance the set of CPDAG candidates and improve their alignment with the ground truth. Experimental results on both simulated and real-world datasets demonstrate that CPDAG-GFN performs competitively with established methods for learning CPDAG candidates from observational data.

Published in Transactions on Machine Learning Research (06/2025)
Learning Equivalence Classes of Bayesian Network Structures with GFlowNet
Michelle Liu
2michelle. Hinihelll.liu@@mmal.. com com
Mila Québec AI Institute
Zhaocheng Zhu
Shaocheng.zhu@@mmlt.. quebec.
Mila Québec AI Institute
Olexa Bilaniuk
aleza.bilaniukkmmii...o quebee
Mila Québec AI Institute
Emmanuel Bengio
Valence Labs
Reviewed on OpenReview: /ttps://openeee
// opeereveew.eeee... net/ forum? id- FAccToAdaa
Abstract
Understanding the causal graph underlying a system is essential for enabling causal infer- ence, particularly in fields such medicine and genetics. Identifying causal Directed Acyclic Graph (DAG) from observational data alone is challenging because multiple DAGs can encode the same set of conditional independencies. These equivalent DAGs form Markov Equivalence Class (MEC), which represented by a Completed Partially Directed Acyclic Graph (CPDAG). Effeetively approximating the CPDAG is crucial because fa- cilitates narrowing down the set of possible causal graphs underlying the data. We intro- duce CPDAG-GFN, a novel approach that uses Generative Flow Network (GFlowNet) to learn posterior distribution reward CPDAG candidates that approximate the ground truth, with rewards determined by score function that quantifies how well each graph fits the data. Additionally, CPDAG- GFN incorporates a sparsity-preferring filter to enhance the set of CPDAG candidates and improve their alignment with the ground truth. Experimental results on both simulated and real-world datasets demonstrate that CPDAG-GFN performs competitively with established methods for learning CPDAG candidates from observational data.
CPDAGs. From this distribution,
sample high-
1 Introduction
Causal graphs produced from observational data are highly sought after, because knowing the causal dag underlying system enables counterfactual reasoning, allows predictions about the system, and may enhance the generalizability of machine learning models (Schölkopf et al. 2021)
A causal structure typically represented by a Directed Acyelic Graph (DAG). However, significant challenge arises bocause is often impossible to determine which DAG represents the true causal structure from observational data alone. This occurs because multiple DAGs can encode the same set of conditional independencies, making them equally valid representations of the causal structure. Consequently, DAGs that encode the same set of conditional independencics can be grouped into single class known as Markov Equivalence Class (MEC) (Castelletti el al. 2018). Thus, from observational data alone, we can learn a causal graph only up to its MRC (Chickering 2002a Koller & Friedman, 2009
While commonly the that DAGs be learned only up their Markov Equivalence Class (MEC) from obscrva- tional data alone, there special cases under certain conditions where identification is possible. For detailed examples, Shimizu al. (2006); [ooye et (2008); Peters Bühlmann) (014).

---

Published in Transactions on Machine Learning Research (06/2025)
A MFC is represented by a Completed Partially Directed Acyelic Graph (CPDAG. Castelletti et al. 2018 see Figure Dp. Popular methods, such as the PC algorithm (Spirtes et al. 2001 typically identify only a single CPDAG from observational data, potentially overlooking other promising candidates. Like all algorithms, these methods rely on certain assumptions for optimal performance, some of which are challenging to meet in practice. For instance, the PC algorithm often requires unrcalistic conditions, such as infinite data or perfect oracles for independence tests conditions that are difficult to meet in practice. Consequently, these methods may fail to accurately identify the true CPDAG. If the true causal structure falls into a different equivalence class than the one predicted by the model, sticking to one class may overlook potential better-fitting models. Given this limitation, an algorithm that returns multiple CPDAGs from observational data is preferable.
One approach is to adopt a Bayesian method to obtain a posterior distribution over all possible CPDAGs, allowing for the sampling of multiple CPDAGs that could explain the data. In this spirit, we propose to combine Bayesian approach and a filtering mechanism. While our approach shares a connection to the GFlowNet framework, it is fundamentally different from methods like DAG-GFN H
Deleu et al. (2022) introduce a novel approach called DAG-GFN, which uses GFlowNet with a uniform prior to approximate the posterior distribution over DAGs from observational data, where probabilities are approximately proportional to the reward y The reward is determined by a score function that measures how well a DAG fits the observations. The better the fit, the higher the probability of sampling that DAG. CPDAGs can be obtained by converting the sampled DAGs to CPDAGs.
One drawback that stems from using this approach is primarily due to its reliance a score function and uniform prior. Since the posterior distribution trained by DAG-GFN is approximately proportional to the density induced by the score function, the learned distribution is heavily influenced by this function. If the score function assigns high scores to many DAGs, including those not representing the ground truth and potentially even those with higher scores than the ground truth (a scenario likely to occur in settings with insufficient observational data (Friedman & Koller] (003)), the posterior distribution may become skewed, diverging significantly from the true distribution underlying the data. In other words, it is likely that our prior over graphs matters. In DAG-GFN, the choice of uniform prior treats all DAGs as equally likely, not incorporating any knowledge that could guide the model toward a more accurate distribution. This can lead to poor approximations of the dataset's underlying distribution, resulting in samples that may not adequately reflect the true graph.
In this paper, we roduce a new algorithm called CPDAG-GFN, which uses GFlowNet to produce sets of CPDAG candidates from obscrvational data. Unlike DAG-GFN, which searches within the DAG space, our approach operates directly in the CPDAG space, enabling direct CPDAG sampling. Moreover, instead of relying on the posterior to produce final set of candidates, as in DAG-GFN, we rely on the posterior as amortized sampler from which we can select an ideal set of candidates. In particular, our approach yields relatively high top-K scoring CPDAGs from this amortized sampling. This is possible because GFlowNets can be seen as amortized samplers capable of exploring multiple high-reward states (e.g., scores) during training.
As mentioned above, relying solely on scores to prioritize graphs may lead to discrepancics with the ground truth, as high-scoring graphs might significantly deviate from it. To address this, we refine the sampled candidate graphs by incorporating additional knowledge into our CPDAG-GFN algorithm. One can think of this as imposing a prior belief into our CPDAG-GFN algorithm, though not in the Bayesian sense. Specif- ically, we enhance our CPDAG-GFN algorithm by applying a heuristic filter, removing the least common edges among the sampled graphs. This additional step is based on the conjecture that the top-K graphs sampled from GFlowNet often share common edge features likely present in the true graph, helping to align the top-K scoring graphs more closely with the actual CPDAG underlying the data.
We discussed DAG-GFN in the introduction due its use of the GFlowNet framework, which is also central to our approach, though it is not the direct motivation for our work. 3 For further details on how DAG-GEN and CPDAG-GEN differ, refer Appendix K
2

---

Published in Transactions on Machine Learning Research (06/2025)
The contributions of this paper as follows: We introduce novel algorithm named CPDAG-GEN, designed to learn multiple CPDAG candidates from observational data. We evaluate our method using both synthetic and real-world datasets and demonstrate that it performs competitively with established methods.
2
Preliminaries
In this section, we review the concepts relevant to our proposed method, CPDAG-GEN.
2.1 Bayesian networks, Markov Equivalence Class, CPDAGs
A Bayesian network Pearl 2009 Koller & Friedman 2009 is probabilistic graphical model represented by DAG over a set of random variables XI...., X,, Each variable X; is associated with a collection of conditional distributions given its parent nodes, denoted as Pa(X,) [
The dependency structure of a Bayesian network leverages the Markov Property, which asserts that cach variable X, is conditionally independent of uon-descendants in the graph, given its parents Pa(X;). This property allows us to factorize the joint distribution of the network into the product of conditional probabilities for each node given its parents (Jin
al. 2023
X2, ................................ X,) II P(x, Pa(X.))
Markov Equivalence Classes (MECs): DAGs that encode the same conditional independencies are Markov equivalent and are said to belong to the same MEC. These DAGs induce the same joint distribution (Jin al. 2023) DAGs that Markov equivalent share the same skeleton and v-structures (see below for definition).
CPDAGs: A MEC is represented by a CPDAG, also known as an essential groph (Castelletti et al. 2018) A CPDAG is type of partially directed graph that may consist entirely of directed edges, entirely of undirected edges, or a combination of both. It primarily consists of the following three types of edges:
Directed edge: If an edge y appears in every DAG in the MEC, then the CPDAG contains directed edge r y--
Undirected edge: If the edges x + y and - x cach appear in at least one DAG in the MEC, then the CPDAG contains an undirected edge between x and y.
V-structure: If an ordered triple nodes (x, 2) forms a configuration where x + + and x and æ are not connected by any edge, then this configuration is classified as v-structure (Pearl 2009
The following theorem provides necessary and sufficient. conditions for graph be the CPDAG of some MEC, which is essential for defining the search space for CPDAG-GPP GFN algorithm in Section 3.2.1
Theorem 1 (Andrsson et al. 1997 )) A gruph G is CPDAG if and only if il salisfies all of the following four conditions:
(a) G contains no directed cycle.
(b) Every chain component of chordal.
(c) The graph a b e does not occur as an induced subgraph of G.
(d) Every directed edge + b in G is strongly protected in G
Note that not every partially directed graph qualifies CPDAG of some MEC, as indicated in the theorem above.
4Pa(X;) represents the collection of values of all parent nodes; for node without parents, this set empty.
The skeleton of DAG refers to the undirected graph obtained by ignoring the direction of all edges in the DAG.
6 Refer to Andersson al. (1977 for the definition of 'strongly protected and review of the terms (b) above.
3

---

Published in Transactions on Machine Learning Research (06/2025)
variables
MECs
MECs/DAGs
GO: X1
1.00000
X1
X2
X3
0.66667
G2: X1 X2 X3
11
0.44000
185
0.34070
MEC
CPDAG X1LX3 X2
8782
0,29922
X1LX3 X2
1067825
0.28238
31251057
0.27443
2121334052000
0.27068
32626056291213
0.26888
Figure 1: Illustration of a MEC and its correspond- ing CPDAG for variables. The MEC consists of multiple DAGs (i.e. Go, G1, G2) that share identical conditional independencies, represented by X1 1 X3 X2. The CPDAG is single graph that compactly represents these DAGs, encapsulating the same conditional independencies.
111890205449577614
0.26799
The number of CPDAGs a function of the number of variables. The column labeled "MEC/DAG" represents the ratio between the num- ber of CPDAGs and the number of DAGs for each variable count (Gillispie Perlman 2002
Figure 2:
2.2 GFlowNet
Generative flow networks (Bengio et al. 2021 2023), or GFlowNets, were introduced as a framework to learn to sample from an unnormalized density function, lypically referred to as the reward R(s) in Gel literature, by decomposing the generative process in a trajectory of constructive steps. GFlowNets work by modelling the flow that goes through the network representing the space of possible constructions, accounting for all possible construction orders of an object. We introduce the framework for a discrete setting, but continuous settings are also possible (Lahlou et al. 2023
In GFlowNet the state space is defined by a pointed DAG, which we denote H = (S,A), with unique initial state E S and some terminal states X' C on which R: X' - I2 the reward function is defined. We define the exact state space we use in Section 3.2.1 but note that the GFlowNet DAG is distinct from the (CP)DAGs presented above; fact, states within H are themselves (CP) Elements of the action space (s s') E A denote valid constructive steps, such as adding a directed edge a CPDAG (see Figure 3 or may represent the action of ending generation. GFlowNets define a forward policy used for sampling objects, (s(ssss), backward policy Ps(s)s') (a policy on the reverse Markov decision process, i.e., model giving a distribution over the parents of any state), and an estimate of the partition function Z representing the sum of all rewards-an and the total flow when interpreting H. as network. The policy PF determines a terminating distribution PJT over X, which is the marginal distribution over the final states of trajectories sampled following PF (i.e., those at which the termination action is taken).
GFlowNets are trained by driving model to respect constraints which preserve the flow within H. One such set of constraints the trajectory balance constraints (Malkin et al. 2022), whereby for any trajectory (su
8n z):
n I
Pr (1441/))) = F(S.) II (B(()(5441)
(2)
where F(s,)= = R(x) is the flow the terminal (sink) state æ. With the above constraints satisfied, sampling transitions starting from So and using Pp guarantecs that the marginal terminating distribution PJ (a)) x R(x).
In the present work parameterize log Zo and P), uniform PB, and apply the trajectory balance objective (Malkin et al. 2022), which for trajectory (so +
8n x) is:
Zp IIr' PF (s1; CTB(T) = (log
(3)
R(x) II PB (p((118411)
4

---

Published in Transactions on Machine Learning Research (06/2025)
When training with GelowNet objectives, samples trajectories from some behaviour policy (which may either coincide with Pr on-policy training, as done in this paper or use off-policy exploration) and performs gradient descent steps on the loss, in our case the one in 3
3
Method
The goal of CPDAG-GIN is to return multiple CPDAGs that approxinate the true CPDAG underlying the data. The objective of using GFlowNet is to construct a posterior distribution over CPDAGs that will allow us to sample high-reward CPDAGs. GFlowNet is suitable for this because of its capabilities as an amortized sampler, which allows for sampling during the training process and facilitates the exploration of high-reward CPDAGs throughout. Since the lop K sampled high-scoring CPDAGs may oflen not align well with the true CPDAG underlying the data Koller & Friedman (2009), we incorporate heuristic filter into our algorithm.
explorati
3.1 Heuristic Sage-SSp Filter
We introduce a heuristic filter that removes the L least common edges among the top sampled graphs the end of training, while ensuring that each removal does violate CPDAG properties in [ thereby maintaining the graph's validity our observation that edges consistently appearing across top K high-scoring models tend to reflect shared patterns in the true underlying graph. This observation led us to hypothesize that high-scoring graphs may share common edge features with the true CPDAG. The filter targets edges that do not consistently appear across models, which may mitigate the presence of spurious edges in the sampled graphs.
CPDAG. L is hyperparameter. This approach motivated by
3.2 GFlowNet setup
The setup for GFlowNet includes defining state space, reward function, a graph neural network (GNN), and a loss function. For the loss function, we employ the trajectory balance function, which is covered in We will now discuss each of these components in turn.
Section 2.2
3.2.1
State space
We define the state space to consist solely of CPDAGs, and the GFlowNet's action space transitions from one CPDAG graph to the next.
Recall from Section 2.1 that a CPDAG may consist entirely of undirected edges, solely of directed edges, or a combination both directed and undirected edges. We thus use the following three actions: add a directed edge, add an undirected edge, apply the makeV operator which transforms a graph structure from x - y - z to y + In Appendix A we show that these three actions are enough to construct any CPDAG in the search space.
In CPDAG-GFN, graphs are built starting from an edge-less graph so, with transitions to new state achieved by applying one of the three actions mentioned above. For any given state, we limit allowable actions to those that lead to a new graph satisfying all the CPDAG properties outlined in Theorem section
This ensures that the graph resulting from any permitted action will also be a CPDAG.
Additionally, we introduce stop action, which serves as the termination point for trajectory through the state space. If a stop action is sampled in 8,, we consider the state terminal and compute its reward R(s+)
(see Figure 3
3.2.2 Reward function
Let D represent a dataset of d. observations. Since we aim to sample CPDAGs that fit the data well, we define the reward as the score function R(G) score(G. D). We follow the definition of the score function by Koller & Friedman b2009h:
score(G, (G, D) P(D G)P(G),
(4)
5

---

Published in Transactions on Machine Learning Research (06/2025)
masheV
23
add in
31
32
udd i2
32
add imadid action
add 21
F1
G1
01
G5
33
add
add 21 17
Stop
Go
G3
R5
R(Ga)
G1
Figure 3: This figure illustrates the CPDAG construction process during GFlowNet training. Tt. shows transitions from an initial edge-less graph state Go to subsequent states, distinguishing between valid actions that lead new CPDAGs and invalid actions prohibited because they result in non con-CPDAG states. Sampling stop action at state G3 concludes the trajectory, with the reward R(G3) then computed.
where P(G) a structure prior which we set be uniform. This configuration enables GFlowNet to explore the space of CPDAGs without any initial bias, and is a common choice (Eggeling al, 2019 Koller & Friedman 2009 Deleu et al. 2022).
The marginal likelihood P G) can be calculated using any score-equivalent function such as the BGe
Geiger & Heckerman, 1994), the BDe score (Heckerman et al. 1995 Chickering, To obtain score for a CPDAG, we first find a DAG belonging in the MEC that this CPDAG represents using an algorithm by Dor Tarsi 1992). then assign that score to the CPDAG.
score Kuipers et al., 2014
2013
3.2.3
Parameterization with graph neural networks
In GFlowNet, we need to learn a policy that gives the probability each state. Considering the exponential number of CPDAG states, it impossible to store all these probabilities a lookup table. Meanwhile, the training trajectories may not cover every state the CPDAG space, which mcans we have to predict the probability for unseen states at Lest time. Following previous works Bengio el al. (2021); Deleu al. (2022) parameterize the policy with neural network over the graph structure of the current state.
Considering the directed nature of CPDAGs, we employ a relational graph neural network (RGCN) Schlichtkrull et al. (2018) to encode the node represenlations, where directed and undirected edges are treated as different relations. For any node u, RGCN iteratively computes its representation h, with the following message passing stop
((+1) 4
ΣΣ PER.EN.(C)
[N-(W] W w
(5)
where R = (directed, directed undirected) is the set of relations, (N) is the set of nodes connected by relation from node u, w and ( are learnable matrices and is the activation function. The input embeddings ha are initialized with one-hot embeddings to distinguish different nodes in the graph.
The three actions in Sec 3.2.1 correspond to link prediction and graph classification tasks on graph structure. Therefore, we decode the actions of adding edges with SimplE. score function Kazemi & Poole (2018) 20,8), a common choice for relational link prediction. Specifically, SimplE computes the following for a head node u,
7Other scoro-oquivalent functions that is, those that assign the same for any Markov-cquivalent graphs such the Akaike information criterion (AIC) AAkike 1974,, the Bayeslan information criterion (BIC) Schwarz 1978 the minimum description length (MDL) (Rissanen 1986), elc.

---

Published in Transactions on Machine Learning Research (06/2025)
relation r and a tail node
score(u, 0) = (h, 2
Kh, Th,
(6)
where v, is a learnable embedding for relation r, @ is element-wise multiplication and K is an anti-diagonal identity matrix. Thanks to the asymmetry of the anti-diagonal kernel, SimplE can have different predictions for r,, u) and (v, r, u), thereby is suitable for the action of adding directed edges in our model. To accommodate the action of adding v-structure, set of two nodes u1, W2 and collider node i.e. predicting ((11, u2), v)). The stop action is modeled by a multi-layer perceptron (MLP) over the graph representation, which is obtained by a min pooling operation applied over all node representations in the graph.
consider it a link prediction problem between a
4 Experiments
In this section, we empirically assess CPDAG-GEN's performance against established methods by comparing the learned CPDAGs to real-world proteomics dataset obtained from protein signaling networks (Sachs et al. 2005). J. Additionally, we evaluate our method on synthetic datasets across different settings (e.g., data size, noise level, network topology). It. is important to note that our goal is not to analyze the specific conditions under which our method outperforms baselines, but rather to evaluate CPDAG-GFN's perfor- mance in different scenarios. Experimental results show that CPDAG-GFN performs competitively against established baselines in these settings.
4.1 Experimental evaluation
Evaluation metric We adopt the evaluation metries used in prior work (Deleu et al. 2022 Lorch et al.
2021]. We assess the performance of each algorithm using the Expected Structural Hamminng Distance (E-HD)- - which measures the discrepancy between the inferred and the true CPDAGs (see Appendix B for further detail), with lower F-SHD indicating better performance-an the Area Under the Receiver Operating Characteristic curve (AUROC), where higher value signifies better performance. Additionally, compute the average Structural Hamming Distance (SHD) between all pairs of CPDAGs in the sample, providing measure of average dissimilarity across the CPDAGs. While this distance is not formal evaluation metric, it provides insight into the diversity of the sampled graphs, with a higher average indicating greater dissimilarity.
O
Baselines To provide comprehensive evaluation of our proposed method, we have selected baselines that use different approaches for approximating distributions over structural models. We include bootstrapping
with PC (Spirtes et al. 2001) and Greedy Equivalence Search (GES) CChickering 2002b). Additionally, we
employ DAG-GFN (Deleu et al.] 2022), which leverages GelowNet: DiBS (Lorch et al. 2021), which uses
a variational inference approach; and MC3 (Madigan et al. 1995 Giudici & Castelo
2003): representing
MCMC-based methods.
4.2 Evaluation on synthetic data
In our experiments, we use the BGe score function as our reward function. Following Lorch et al. (202) we generate ground truth networks using linear- Gaassian Bayesian networks, with their structures sampled according to the Erdös-Rény: (ER) model (ERDdS & R& 1959) and the scale-free (SF) model (Barabási & Albert, 1999). These models were selected for their contrasting structural properties to ensure diverse evaluation of CPDAG-GFN's adaptability and efficacy across different network topologies. In addition, we designed our experiments to include several scenarios: different observational data sizes ranging from small (100) to large (a million) to demonstrate scalability, varying levels of noise in the data from small (0.01) to moderate (0.1), and different. network complexities with expected degrees of 1d, 2d, and 3d, where d is the number of nodes, in which we set to d=10 in our experiments. For each experimental run, we sample K graphs, with K set to 100. Performance metrics (o.g. E-SHD and AUROC) are derived from 10 distinct datasets, each one generated from a unique Bayesian network. Performance results are presented in Figures 1-5, which indicate that our algorithm performs competitively.
7

---

Published in Transactions on Machine Learning Research (06/2025)
aMillionData, ER-degl, no1se-0.1
aMillionDaaa, ER-degl, noise-0.1
DMillinDData, ER-degl, noise-0. 0.1
1.00
F.SHD
AUROC
0.95
distance
30
0.90
0.85
0.80
0
B.PC
B-OES
Ditis
MCa
DAG-GFN
CYDAGOOFN
B-PC
B-OES
DiBs
Mrd
DAG-GFN
CPDAG-GFN
B.PC
B-GEs
DiBs
Mco
DAGAGFN
CRDAG-OFN
Comparison of E-SHD and AUROC metrics for a dataset generated from million observations using a ground truth graph sampled from an Erdös-Rénn Rényí model (ER-degl) with a noise level of 0.1. Lower E-SHD and higher AUROC preferred. A higher distance in the third figure indicates greater dissimilarily among the graphs.
Figure 4:
Dbsaata, ER-deg2, noise=0.1
100 obsData, ER-deg2,
noise=0.1
100 obs ER-deg2, noise
0.96
E-SHD
AUROC
dislance
24
0.80
0.72
12
0.64
B-PC
B-GES
DiBs
MC
DAG-GPN
CPDAG-OPN
B-PC
B-GES
DIBS
MC²
DAG-OFN
CADAG-GEN
B-PC
B.GES
DiBS
Me3
DAG-OFN
CDDAG-OPN
Figure 5: Comparison of E-SHD and AUROC metrics for a dataset generated from 100 observations using a ground truth graph sampled from an Crdös-Rémy model (ER-deg2) with a noise level of 0.1. Lower E-SHD and higher AUROC are preferrod. A higher distance in the third figure indicates greater dissimilarity (c.g. more diversity) among the graphs.
100 ohsaata, ER- n.05
100 obsData, ER ER-deg2, noise-0.01
100 obslata, ER-deg2, noise-0.00
0.96
E-SHD
AUROC
0.88
distunce
30
0.80
15
0.72
B.PC
B-OES
DiBi
MC
DAG-GEN
CPDAG-GFN
B.PC
B-OES
DiBS
MC
DAG-GEN
CPDAG-OFN
B.PC
B-GES
DIBS
Mca
Dag-GFN
CRDAG-OFN
Figure 6: Comparison of E-SHD and AUROC metrics for dataset generated from 100 observations using ground truth graph sampled from an Frdös-Rényi model (FR-deg2) with noise level of 0.01. Lower F-SHD and higher AUROC are preferred. A higher distance in the third figure indicates greater dissimilarity among the graphs.
4.3
Real world data: Protein network from cell data
A widely used benchmark in structure lcarning is the Sachs datasct (Sachs et al. 2005), together with its reference network of 11 proteins and 17 edges. Sachs el. al. (2005) used Bayesian network inference with intervention data to reconstruct signaling pathways and compared their learned network to a reference network assembled from prior biological pathways reported in the litcrature. Their reconstruction largely reflects these pathways, although three well-establisher edges (PIP, PKC, PLC-> + PKC, PIP: Akt) were not recovered. This reference network, her with the Sachs dataset, has since become widely
8

---

Published in Transactions on Machine Learning Research (06/2025)
100 Data SF deg3, noise-0.1
100 obs SF- deg3, noise-0.1
100 obs SF-dee3 noise-0.
0.88
E-SHD
52
AUROC
0.80
distance
52
24
0.72
0.64
16
B.PC
B-GES
DiBS
MC
DAC-GFN
CPDAG- GPN
0.56
B-PC
B-GES
DIDS
MC
DAG-GFN
CPDAG- GPN
B-PC
B-GES
DiBS
MC3
DAG-GFN
CPDAG-GFN
Figure 7: Comparison of E-SHD and AUROC metrics for dataset generated from 100 observations using ground truth graph sampled from scale-free model (SF-deg3) with noise level of 0.1. Lower E-SHD and higher AUROC are preferred. A higher distance in the third figure indicates greater diversity among the graphs
Method
[[SHD]
AUROC
E Edges]
MC
39.32 + 1.79
0.645 0.041
39.46 + 0.97
Bootstrap GES
19.74 0.097
0.751 # 0.011
11.11 = 0.090
Bootstrap PC
17.61 0.23
0.728 + 0.019
8.45 + 0.335
DIBS
13.28 0.17
0.756= 0.017
11.47 + 0.34
DAG-GFN
18.92 0.019
0.658 + 0.019
23.02 + 0.14
CPDAG-GEN
16.61 + 0.65
0.757 0.029
15.42 + 0.61
Table 1: Inference of protein signaling pathways from cytometry data (aachs al. 2005) Metrics are the mean SD of 10 experimental run
used benchmark in the causal discovery community, providing common basis for evaluating algorithms real-world biological data.
In this section, we evaluate our work using this widely used benchmark. The dataset consists of N = 854 continuous observations. The results, presented in Table 1, compare the evaluation metrics E-SHD) and AUROC of CPDAG-GEN against the baselines. For AUROC, a higher value is better, and for E-SHD, a lower value better.
CPDAG-GFN demonstrates competitive performance against the other methods, achieving an E-SHD of 16.61 + 0.65. Notably, while DiBS achieves the lowest E-SHD, it predicts only 11.47 edges average. In contrast, CPDAG-GFN's edge count of 15.42 + 0.81 is closest to the ground truth network, which consists of 17 edges. Although AUROC values for DiBS, Bootstrap GES, and CPDAG-GFN are relatively close, CPDAG-GFN performs competitively by achieving a relatively low E-SHD, high AUROC, and an edge count closer to the ground truth compared to other baselines.
5 Related work
Markov Chain Monte Carlo (MCMC) Earlier papers that explored structure learning in the space of CPDAGs by means of MCMC include: Madigan et al. (1996) and Castelo & Perlman (2004). A more recent approach is by Castelletti et al. (2018). The paper focuses learning sparse CPDAGs. To enhance the structure learning of these CPDAGs and ensure the graphs remain sparse, the authors introduce sparsity constraint. This constraint limits the CPDAG space to subspace where the number of edges docs not exceed 1.5 times the number of nodes in the graph. While this approach can be effective, it can be a drawback in scenarios where the gettraaienr process is more complex and less sparse. In such cases, the constraint may bias the lcarning towards sparse graph that fail to capture more complex relationships within the data. Another draw back of using MCMC methods is their tendency to become trapped in single mode of high probability SSed 2022 restricting their ability to explore diverse graph structures across different. regions
9

---

Published in Transactions on Machine Learning Research (06/2025)
of high-probability modes. By using the GFlowNet approach instead of MCMC, the method we propose mitigates being confined to a single mode.
Point estimate methods Two widely known point estimate methods for computing a CPDAG from observational data are constraint- based methods and score-based methods. Constraint- based methods, such as the PC (Peter and Clark) algorithm and the Fast Causal Inference (FCT) algorithm &Spirtes et al.) 2001) rely on conditional independence tests to identify the CPDAG that represents causal structures consistent with a given dataset (Eberhardt, 2017 In contrast, score-based methods, such as the Greedy Equivalence Search (GES; Chickering] (2002b)), ) rely on a score function. These methods traverse the space of CPDAGs, assigning scores to graphs to measure their fit to the data. At each step, an edge is either added, removed, or reversed. As the name suggests, the search is greedy, choosing the stale with the highest score to progress.
Amortized sampling methods Recent approaches to Bayesian structure learning that approximate the posterior distribution over DAGs include DAG-GFN (Deleu al., 2022) and DiBS (Lorch et al., 2021). both operate within the space of DAGs. The DiBS method employs variational approach, representing DAGs in continuous latent space to facilitate the learning of the posterior distribution over network structures. Conversely, the DAG-GFN method uses GFlowNet to achieve a posterior distribution over DAGs where probabilities are approximately proportional to assigned rewards. CPDAGs can be obtained by converting the sampled DAGs to CPDAGs.
6 Conclusion
We have introduced a novel method for learning CPDAG candidates underlying observational data using GFlowNet. To better align the candidates with the ground truth, we applied a heuristic filter by removing the least common edges from the sample. Unlike traditional methods that produce single CPDAG, our approach generates multiple CPDAG candidate structures by sampling directly from CPDAG distributions. In future work, we aim to explore the integration of domain-specific knowledge into the CPDAG-GFN algorithm. This could involve incorporating Bayesian priors to guide the sampling process toward more plausíble causal structures, or developing heuristic-based constraints that reflect expert knowledge. By further incorporating specific causal hypotheses within the model, we hope to improve the accuracy and relevance of the generated CPDAGs, particularly in applications where expert knowledge available.
Acknowledgments
We would like to thank Kolya Malkin for the fruitful discussions that led the proof in Appendix A and for his feedback manuscript. We also thank members of the Mila community, including Mizu Nishikawa- Toomey, Mansi Rankawat, Tristan Deleu, Fabrice Normandin, Jithendaraa Subramanian, Anirudh Goyal, Guillaume Huguet, Paul Bertin, Alex Tong, Jason Hartford, Simon Lacoste-Julien, Antonio Gois, Ionelia Buzatu, Philippe Brouillard, Michael Przystupa, Victor Schmidt, Shruti Joshi, Divyat Mahajan, and Rabiul Awal for their help and support.
References
Hirotugu Akaike. A new look at the statistical model identification. IEEE transactions on automatic control, 19(6):716 723, 1974.
Stoen A Andersson, David Madigan, and Michael D Perlman. A characterization of markov equivalence classes for acyelic digraphs. The Annals of Statistics, 25(255505 541, 1997.
Yashas Annadani, Nick Pawlowski, Joel Jennings, Stefan Bauer, Cheng Zhang, and Wenbo Gong. Bayes- dag: Gradient-based posterior inference for causal discovery. Advances in Neural Information Processing Systems, 36:1738 -738-163,, 1763, 2023.
Albert-Lászile Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439): 009-512, 1999.
10

---

Published in Transactions on Machine Learning Research (06/2025)
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 14:27381-27338
2021.
Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward J Hu, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations. Journal of Machine Learning Research, 24(210):1-55 2023.
Federico Castelletti, Guido Consonni, Marco Della Vedova, and Stefano Peluso. Learning markov equiva- lence classes of directed acyclic graphs: an objective bayes approach. 2018.
Robert Castelo and Michael D Perlman. Learning essential graph markov models from data. In Advances in Bayesian networks, pp. 255 269. Springer, 2004.
The Journal of David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-554 2002b.
David Maxwell Chickering. Learning equivalence classes of bayesian-network structures. Machine Learning Research, 2:445 498, 2002a.
David Maxwell Chickering. A transformational characterization of equivalent bayesian network structures. arXiv preprint 1rXxi:1302.4000 2013.
Chris Cundy, Aditya Grover, and Stefano Ermon. Bed nets: Scalable variational approaches for bayesian causal discovery. Advances in Neural Information Processing Systems, 34:7095-7110, 2021.
Tristan Deleu, António Góis, Chris Emezue, Mansi Rankawat, Simon Lacoste-Julien, Stefan Bauer, and Yoshua Bengio. Bayesian structure learning with generative flow networks. In Uncerlainly in Artificial Intelligence, pp. 518-528. PMLR, 2022.
Dorit Dor and Michael Tarsi. A simple algorithm to construct consistent extension of partially oriented graph. Technicial Report R-185, Cognilive Syslems Laboralory, UCLA, pp. 45, 1992.
Frederick Eberhardt. Introduction to the foundations of causal discovery. International Journal of Data Science and Analytics, 3:81-91, 2017.
Ralf Eggeling, Jussi Viinikka, Alcksis Vuoksenmaa, and Mikko Koivisto. On structure priors for learning bayesian networks. In The 22nd International Conference on Artificial Intelligence and Stolislics, pp- 1687-1695. PMLR, 2019.
P ERDdS and A R&ww.. On random graphs Publ. math. debrecen, 6(290-297):18, 1959.
Nir Friedman and Daphne Koller. Being bayesian about network structure. orXiv preprint arXiv:1301.3856, 2013.
Dan Geiger and David Heckerman. Learning gaussian networks. In Uncertainty Proceedings 1994, pp. 235-243. Elsevier, 1994.
Steven B Gillispic and Michael D Perlman. The size distribution for markov equivalence classes of acyclic digraph models. Artificial Intelligence, 141(1-2):137 155, 2002.
Paolo Giudici and Robert Castelo. Improving markov chain monte carlo model search for data mining. Machine learning, 50:127-158 1588, 2003.
David Heckerman, Dan Geiger, and David M Chickering. Learning bayesian networks: The combination of knowledge and statistical data. Machine learning, 20:197-243, 1995.
Patrik Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. Advances in neural information processing systems, 21, 2008.
11

---

Published in Transactions on Machine Learning Research (06/2025)
Zhijing Jin, Jiarui Liu, Zhiheng Lyu, Spencer Poff, Mrinmaya Sachan, Rada Mihalcea, Mona Diab, and Bernhard Schölkopf. Can large language models infer causation from correlation? arXiv:2306.0588 2023.
or Xiv preprinl
Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. Advances in neural information processing systems, 31, 2018.
Daphne Koller and Nir Friodman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Jack Kuipers, Giusi Moffa, and David Heckerman. Addendum on the scoring of gaussian directed acyclic graphical models. 2014.
Salem Lahlou, Tristan Deleu, Pablo Lemos, Dinghuai Zhang, Alexandra Volokhova, Alex Hernándee-Garcca Léna Néhalc Ezzine, Yoshua Bengio, and Nikolay Malkin. A thcory of continuous generative flow networks. In International Conference on Machine Learning, pp. 18269 18300. PMLR, 2023.
Lars Lorch, Jonas Rothfuss, Bernhard Schölkopf, and Andreas Krause. Dibs: Differentiable bayesian struc- ture learning. Advances in Neural Information. Processing Systems, 11224111-24121 2021.
David Madigan, Jeremy York, and Denis Allard. Bayesian graphical models for discrete data. International Slatistical Review/Revue Internationale de Stalistique, pp. 215-232, 232, 1995.
David Madigan, Steen Andersson, Michael D Perlman, and Chris T Volinsky. Bayesian model averaging and model selection for markov equivalence classes of acyclic digraphs. Communications in Statistics- Theory and Methods, 25(1))22493 2519, 1996.
Nikolay Malkin, Moksh Jain, Emmanuel Bengio, Chen Sun, and Yoshua Bengio. Trajectory balance: Im- proved credit assignment in gflownets. Advances in Neural Information Processing Systems, 35:5955 5967, 2022.
Judea Pearl. Causality. Cambridge university press, 2009.
Jonas Peters and Peter Bühhlmann. Identifiability of gaussian structural equation models with equal error variances. Biometrika, 101(1):219 228, 2014.
Jonas Peters and Peter Bühlmann. Structural intervention distance for evaluating causal graphs. Neural computation, 27(3)777- 2015.
Jorma Rissanen. Stochastic complexity and modeling. The annals of stotistics, pp. 1080-1100, 1986.
Karen Sachs, Omar Perez, Dana Pe'er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 308 2005.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In The Semantic Web: 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3 2018, Proceedings 15, pp. 593 607. Springer, 2018.
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEEE, 109(5): 612-634, 2021.
Gideon Schwarz. Estimating the dimension of model. The annals of stotistics, pp. 461-464, 1978.
Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non- gaussian acyelic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, prediction, and search. MIT press, 2001.
Saifuddin Syed. Non-reversible parallel tempering on optimized paths. PhD thesis, University of British Columbia, 2022.
12

---

Published in Transactions on Machine Learning Research (06/2025)
Ioannis Tsamardinos, Laura E Brown, and Constantin F Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Machine learning, 65:31-74 2006.
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric Xing. Dags with no tears: Continuous optimization for structure learning. Advonces in newral information processing systems, 31, 2018.
13

---

Published in Transactions on Machine Learning Research (06/2025)
A Sufficiency of actions to traverse CPDAG search spaces
In this section, we demonstrate that the three traversal actions-adie a directed edge, adding an undirected edge, and applying 'make V" operators are sufficient to reach any CPDAG within the search space. To do so, we introduce the following two propositions:
Proposition 2 (Andersson et al. [1997)). Let G and H be two CPDAGs graphs with the same vertex set V. Then there exists a finite sequence = GI...., Gk = H of CPDAGs with verter set V such that each conseculive pair of G G4+1 differs by one of the three traversal traversal actions: add directed edge, add undirected edge, or makeV.
Building upon the aforementioned proposition, we present the following proposition:
Proposition 3. For any essential G, there erists a sequence of graphs Gu...., Gn such that:
Go the gruph with no edges, and =.
Each G, is CPDAG. For each i, G:+1 can be obtoined from G; by of the operators: add directed edge, add undirected edge, makeV.
Proof. This is immediate from the construction in the proof of Andersson's Proposition 4.5, which provides algorithm for constructing such sequence for any G. Note that the statement of Andersson's Proposition 4.5 alone does not imply this result, as it only guarantees sequence G2 such that for each i, either G, is obtained from G1+1 by one of the operators, or G:+1 is obtained from G; by one of the operators.
Proposition above asserts that we can traverse the entire search space CPDAGs starting from the empty graph Gy and using only the three traversal actions (add a directed edge, add an undirected edge, or makeV operation); i.e., every stale reachable from the initial state. Each traversal action either increases the number of edges or does not change the number of edges while increasing the number of directed edges, which implics the scarch space is acyclic.
B Evaluation Metrics
We adopt the evaluation metrics used in prior work (Deleu al. 2022 Lorch et al. 2021 the Expected Structural Hamming Distance (E-SHD) to the ground truth graph g and the Area Under the Receiver Operating Characteristic Curve (AUROC). Following prior work (Deleu et al. 2022 Lorch et al. 2021 the AUROC is computed by thresholding the posterior edge p(gs/ D) at varying thresholds.
Similarly, the E-SHD to the ground truth graph (G*) is defined as:
F-SHD
SHD(G
where n represents the number of unique CPDAGs sampled from the posterior, and Ga denotes CPDAG. The SHD G*) counts the number of edge changes that separate the learned CPDAGs Ga from the ground truth g" (Peters & Bühlmann 2015 Lorch et al. 2021
14

---

Published in Transactions on Machine Learning Research (06/2025)
C Additional experiments
The ground-truth graphs are sampled according to Erdos-Rényi model with average degrees equal to 1, 2, and 3, respectively, denoted ER-degl, ER-deg2, and ER-deg3. Each experiments is ran between 7 to 9
seeds. The DAG-GEN was run using the publicly available code from Deleu et al. 2022
MMiliionDtts, BR-dop2. miiemd
Miillion ohelatt, HRt-de22, mi)eee))
aiiliimlbbs FR-dep3 nounn
aMillieeban ER-der neizeel
AUROe
B-PC
D--ts
Med
DAG-DPN
CRDAG-OPN
B-PC
B-0rs
pabe
Me
DAG-aFN
B-GE3
Duts
MC
DAG-DPM
CPDAG-OFN
B-P
B-GES
Dahs
DAC-aP
100 ebDaas BR BR-depl, T0isem0.
1.
000
Dam, ER degl mi
100 Dat ER-4ez neize
0.78
100
Dam EX dap Risse
8
E
E-0DD
S
E 11100
MURDC
11
0.51
B-P
D-0
Dat0
Mcd
DAG-OPN
CRBAG-OPN
B-P
B-ats
Dans
DAG-OPM
CHRAGOOP
B-029
Date
Me
DAG-aPN
CRAAG-OF
B-p
Da00
MCd
DAC
GDAG-OFF
100 DatDat dedl miss-000
100 obDaa dell m. al
obduats
100 obaaas deg m0000 11
g
E-SHD
8
AURDC
8
g
0.5
B-70
B-G8
Dat
Med
DAG-OPS
CDDAG-ONN
B-7C
B-055
Dins
MC
DAG-ON
CPDAG.OPN
B.
Dins
MC
DAG-GFN
CIAAG-ONN
B-123
Dat
MC1
DAGaON
CROAG-OPS
For the following experiments, the ground-truth truth graphs are sampled according to an scale-free model with average degrees equal to 1 and 2 respectively, denoted SF-degl and degd
100 dbsDats, SF-deel 0.1
100 abiData, SF-deel, n.
100 obeDuta SF-4e22 noise n.1
els SF-dee2 miise al1
50
ESHH
AUROC
8:00
8.70
R4055
DM5
MC
DAG-aPN
MBr OPN
B.CC
Bozs
Dis
Me
DAG-OPN
MBC-GP
B.PC
B-085
DES
DAG Mic.Ow
B.t
B-0n5
D865
MC.
DAC-GFH
MEC:OPI
15

---

Published in Transactions on Machine Learning Research (06/2025)
D DAG vs CPDAG comparison
To ensure a fair comparison, both DAG-GEN and CPDAG-GFN were implemented with the same sctup, including the same optimizer, neural network architecture, and dataset. We used the trajectory balance (TB) loss and BGe score function to train both models. Comparison of F-SHD and AUROC metrics for a dataset generated from large (e.g. million) and small (e.g. 100) observations using a ground truth DAG sampled from an Erdós-Rényí model (ER-degl) and scale-free model.
Since there two important differences between Deleu et al. 2022 's DAG-GEN and work, namely the top-K sampling evaluation and the heuristic filtering, compare four settings
1. Top-K DAGs obtained using Gflownet as an amortized sampler in the DAG space (call it topK- DAG) versus top-K CPDAGs obtained using GFlownet as an amortized sampler in the CPDAG space (topK-epdag).
2. rand-DAG obtained by randomly sampling K DAGs from the posterior distribution learned by DAG- GFN (Deleu et al. 2022,, versus rand-CPDAG obtained by directly random sampling K cpdags from the CPDAG posterior at the end of training.
3. The same in 1, but with the heuristic filter applied.
The same as in 2, but with the heuristic filter applied.
Baselines with plus sign in front indicate heuristic filter has been applicd.
100 Data SF-deg3, noise 0.1
100 obsData, SF-deg3, noise 0.1
0.9
40
E-SHD
AUROC
0.8
24
rosl ros6-DAG
rond- rand-qudag syda
rand spoloo
lopa DAG
topk lppk-DAGG
logi speda
topk -pulg
rond DAG
rond cod-DAG
rand mand-spoogg
tapk 19G DAG
19p.--AGA
tuplic upodae
hopkc-ppoee spddgg
Figure 8: d=10 variables. Lower E-SHD and higher AUROC indicate better performance compared to those
with higher F-SHD and lower AUROC.
4 Million obsData, ER-degl, noise-
Million obsData, ER-degl. noise
30
E-SHD
AUROC
20
0.75
10
mmd-DAG
rond D
rand- Pedd-yddag
rand spddge
loplt DDG
typl DAG
6op spdag
med-DAR DAG
rand-AGr
rand mand-gpdap
rond spulge>
DAG
tgpl DAK-
Ropk spddag
topsCoppdap opdage
Figure 9: d-10 variables. Lower E-SHD and higher AUROC indicate better performance compared to those
with higher E-SHD and lower AUROC.
16

---

Published in Transactions on Machine Learning Research (06/2025)
E Performance Metrics Across Varying L Values
In this section, we analyze how CPDAG-GEN's performance (e.g. E-SHD, AUROC, and distance) varies with different values of L.
Experimental setup for hyperameter L anaysis: In the plots below, a unique Bayesian network was generated using different random sceds to create the data. This data was then used input our CPDAG-GFN algorithm learn 100 CPDAG candidates. We computed E-SHD, AUROC, and distance metrics using these 100 CPDAGs for varying values of T.. The results presented in the plots below. All plots were generated using data from 1 million observations, ER-degl, noise=0.1, and 10 variable setting,
The plots start at L = (e.g., no least common edge is removed). As the hyperpa- rameter L increases, E-SHD initially decreases but begins to rise beyond a cortain point (around L = 40). Similarly, AUROC starts off high but begins to drop as exceeds a specific threshold. On the other hand, the distance plot demonstrates an overall decreasing trend, with noticeable bump the purple scatter plot between 30 and 40. This suggests that removing certain edges may have increased the diversity of the graphs in the sample. Despite this bump, the general trend is downward, as expected, since removing the least. common edges lypically leads to greater similarity among the graphs, resulting in decrease in the distance metric.
Observation:
A suitable range for L would be one that gives low E-SHD and high AUROC, and sufficient diversity in the generated graphs. Having said that, L values ranging between 30 and 40 would be a reasonable choice.
25
0.9
20
B-SH
AUROC
25
0.8
10
0.7
0.6
20
40
20
40
L
30
20
10
20
40
Figure 10: Lower E-SHD and higher AUROC indicate better performance.
17

---

Published in Transactions on Machine Learning Research (06/2025)
F Additional experiments on heuristic filter on other baselines
While the houristic filter was originally designed as an integral part of CPDAG-GEN, we conducted an analysis to assess whether applying the same refinement step to other baseline methods would generally lead to performance improvements in different settings. In this section, we evaluated baseline performance before and after applying the filter and reported the observed effects. Our results different settings show that the the heuristic filter improves E-SHD across all basclines by lowering it. The largest improvements in E-SHD are observed in CPDAG-GFN and Top-K DAGs + The results below highlight that while the heuristic filter provides general improvements across basclines, its effects are pronounced when combined with GFlowNet's amortized sampling approach.
The figures below compare baseline performance before (green box) and after applying the heuristic filter (blue box, indicated by a plus sign).
aMillionData, ER-degl, I, noise=0.1
a Million obsData, ER-degl, noise=0.1
40
1.00
E-SHD
30
AUROC
0.96
0.92
10
0.88
B-CC-
B-OES
B-oss-
MES
ME33
DISS
DiRS-
opp-DAD
Aupi Aopi-DDGG wo Poie
CRDAn-CR
B-PCs
B-GES
B B-GES-
MC3
McSs
wass
pooe
CPDAO -00400-000
Figure 11: Baselines with lower E-SHD and higher AUROC indicate better performance compared to those
with higher E-SHD and lower AUROC. Basclines with plus sign (c.g. blue box) indicate the application of heurisite filer, and green box is without.
100 obsData, ER-deg2, no 0.1
100 obsData, ER-deg2, noise 0.1
0.96
40
0.88
SHD
32
AUROC
0.80
24
0.72
16
0.64
BoPC
B-RC-
MC3
MC3-
DGS
DIBS-
opk
Aupi -DA--DGG- wo. mioe
CPDA0-OPM
B-PCs
B-GRS
B- B-GES-
MC3
MC3-
Daas-
NoR--DAO
wi pour
CRDAG-00
Figure 12: Baselines with lower E-SHD and higher AUROC indicate better performance compared to those
with higher E-SHD and lower AUROC. Basclines with plus sign (c.g. blue box) indicate the application of heurisite filer, and green box is without.
TTop-K DAGs obtained using Gflownet amortized sampler to sample top K high scoring graphs in the DAG space and then converted CPDAGs. It's not be mistaken for DAG-GFN by Deleu al. 2022 Moreover topK-DAG+ the topK-DAG with the heuristic filter applied
18

---

Published in Transactions on Machine Learning Research (06/2025)
100 obsData, ER-deg2, noise=0.01
100 obsData, ER-deg2, noise=0.01
40
0.96
E-SHD
32
AUROC
0.88
0.80
24
0.72
0.64
B.PC
12 B.PC-
B-015--
DIES
Dits-
MC3
MC3:
toplc DAQ
bopk -DA-
we. poin
CPDAG-OR
B.CC
B-PC:
B.GES
B B.0ES-
Das
Dias-
MCS
MC3-
lepk-DAC MAG-
we. .iior
CPOAG-OPE
Figure 13: Lower E-SHD and higher AUROC indicate better performance compared to those with higher E-SHD and lower
with a plus sign indicate the application of the least common edge removal technique, and wo-prior represents CPDAG-GFN without the heuristic filter.
100 obsData, SF-deg3, noise 0.1
100 obsData, SF-deg3, noise 0.1
0.88
36
E-SHI
30
AUROC
0.80
0.72
0.64
18
0.56
B-PC
B-PC-
Gts
B-5ES-
nins
Dins-
MC²
Mc
topi DAG
tepl tepk-DAG: DAG-
so proor
OPDAG-OPN
Burc
BaCs
B-GES
B BEGS-
Dias
nass-
Mcs
Mc²
WoK-DA0 D.0
wwk--AGs
no joir
COOAGOO
Figure 14: Baselines with lower E-SHD and higher AUROC indicate better performance compared to those
with higher E-SHD and lower AUROC. Baselines with a plus sign (e.g. blue box) indicate the application of heurisitc filer, and green box is without.
19

---

Published in Transactions on Machine Learning Research (06/2025)
G Defining the Mask Over Actions with CPDAG constraints
In this section, we discuss how we enforce theorem 1 of the CPDAG at cach state.
To enforce the directed cycle constraint, we leverage the adjacency matrix, transitive closure, and outer product as inspired by Deleu et al. (2022) Appendix C. This process generates a mask matrix, Maskmatrix: with entries of 0 or 1. We adopt the convention that entry (row, col) the Maskmatrix equal indicates that. the directed edge will.
col will not create directed cycle, while entry of 1 means it
We identify the indices of all zero entries (a.b) in Maskmatrix. Each of these indices is fed into the flow chart which carries out the remaining constraints in theorem 1. The flowchart outputs (indicating the action is allowed) or (indicating the action is forbidden), and the Maskactions array is updated accordingly.
The purpose of Maskactions is filter out all invalid actions so that only valid actions are sampled. Once a valid action is sampled and applied to generate a new CPDAG, the adjacency matrix, transitive closure, and mask matrix updated to reflect the new state. Consequently, Maskactious is also updated accordingly.
Input Index (a,b)
is a->b protected in G (e.g. P(b))
Yes
No
Does adding a->b result in the configuration a->b--c as an induced subgraph of G?
Will adding undirected ege between and (e.g. a--b) keep the chain components chordal?
Yes
No
No
Yes
forbid adding a->b, Return
Is the directed edge a->b strongly protected in G?
forbid adding a-b. Return
adding a-b result in the configuration a-bs-c induced subgraph of G?
Yes
No
Yes
No
adding allowed Return
Forbid adding adding both directed edge a->b and
forbid adding a--. Return
Does adding a-- preserve directed arrows in strongly protected
undirected edge a--b Return 1
Yes
No
adding a--b is allowed Return
forbid adding a--b. Return
090 0->1 0->2 1-9
1911
192
290
2+11
2-92
stop
Maskaction
0
1
0
0
0
1
0
0
Figure 15: a) Flowchart illustrating how actions are validated and filtered at each state using the constraints outlined in Theorem 1. The input index(a,b) are the zero entries in the Maskmatrix- Here, a b denotes a directed edge between node and b in graph G, while b denotes undirected edge between them. b) The Maskactions array entries are updated based the flowchart's output, with 0 indicating valid action and 1 indicating invalid action.
9please refer Andersson al. (1977 for further foundational and implementation details.
20

---

Published in Transactions on Machine Learning Research (06/2025)
H Additional baseline: NOTEARS and MMHC
In this section, we compare our work to two well-known point estimate methods that return single graph: DAGs with NO TEARS (NOTEARS) (Zheng et al. 2018) and the Max-Min Hill-Climbing (MMHC) Bayesian Network Structure Learning Algorithm (Tsamardinos et al. 2006).
NOTEARS is differentiable DAG learning method that formulates the structure learning problem a continuous constrained optimization task. Instead of searching over the combinatorial space of DAGs, it introduces smooth and exact characterization of acyclicity using matrix function constraint. This allows gradient-based optimization to be applied directly to learn the DAG structure. MMHC, on the other hand, is hybrid method that combines constraint- maasdd and score-based approaches. It first identifies the skeleton of the graph using the Max-Min Parents and Children (MMPC) algorithm, a constraint- based method. It then applics a greody hill-climbing search with a Bayesian scoring function to orient the edges. We refer readers to the references for further details of the methods.
Both NOTEARS and MMHC are point estimate methods that return single graph rather than a distribution over possible structures. Consoquently, the E-SHD metric reduces to standard SHD in this case, and the distance metric (e.g., the average SHD between sampled graphs) is not applicable.
MillionData, ER-degl, noise 0.1
aMillionData. ER-degl, noise 0.1
1.00
30
AUROC
0.95
E-SIID
20
0.85
0.80
B-PC
B-GES
DiBS
MC3
NOTEARS
MMFCC
CPDAG-OFN
B-PC
B-GES
DiBS
MC3
DAG-GFN
NOTEARS MMHC
CPDAG-GFN
DAG-GF
Figure 16: Lower E-SHD and higher AUROC indicate better performance compared to those with higher F-SHD and lower AUROC.
100 obsData, ER-deg2, noise
100 obsData, ER-dee2, noise 0.1
0.96
36
0.88
AUROC
E-SHD
0.80
0.72
18
0.64
12
B-PC
B-GES
DiBS
MC3
DAG-OPN
NOTEARS MMHC
CPDAG-OPN
B-PC
B-OES
DiBS
MC3
DAG-OFN
NOTEARS
MMHC
CPDAG-GFN
Figure 17: Lower E-SHD and higher AUROC indicate better performance compared those with higher
E-SHD and lower AUROC.
21

---

Published in Transactions on Machine Learning Research (06/2025)
obsData, SF-deg3. noise-0.
100 obs SF-dee3, noise- 0.1
0.88
E-SHD
32
AUROC
0.80
0.72
0.56
B-PC
B-GES
DiBS
MC3
DAG-GEN
NOTEARS MMHC
CPDAG-GPN
B-PC
B-GES
DiBS
MC
DAG-GFN
NOTEARS
MMHC
CPDAG-GFN
Figure 18: Lower E-SHD and higher AUROC indicate better performance compared those with higher
E-SHD and lower AUROC.
ROC curve
1.0
True Positive Rate (TPR)
True Positive Rate (TPR)
0.6
CPDAG-GFN
CPDAG-GFN
DAG-GFN
DAG-GFN
DIBS
DIBS
GES
GES
PC
PC
MCMC
MCMC
noTears
noTears
0.0
0.0
0.2
0.4
0.6
0.8
10
0.0
0.2
0.4
0.6
0.8
1.0
False Positive Rate (FPR)
False Positive Rate (FPR)
Figure 19: ROC curve comparison for different random seeds under the setting of 100 observational data points, 0.1 noise, and SF-deg3.
22

---

Published in Transactions on Machine Learning Research (06/2025)
True Positive Rate (TPR)
True Positive Rate (TPR)
0.-
0.8
CPDAG-GFN
CPDAG-GFN
DAG-GFN
04
0.4
DAG-GFN
DIBS
GES
0.
GES
0.2
PC
PC MCMC
MCMC
noTears
0.0
0.6
0.8 False Positive Rate (FPR)
False Positive Rate (FPR)
Figure 20: ROC curve comparison for different random seeds under the setting of 100 observational data
points, 0.1 noise, and ER-deg2.
10
1.0
True Positive Rate (TPR)
True Positive Rate (TPR)
06
0.6
CPDAG-GFN
CPDAG-GFN
DAG-GFN
DAG-GFN
DIBS
DIBS
GES
GES
02
PC
0.2
PC
MCMC
MCMC
Tears
noTears
0.6
False Positive Rate (FPR)
False Positive Rate (FPR)
Figure 21: ROC curve comparison for different random seeds under the setting of Million observational data points, 0.1 noise, and ER-degl.
J Further Analysis
Recall that CPDAG-GFN consists of two steps: (1) using GFlowNet as an amortized sampler sample top-K high-scoring CPDAGs, and (2) applying heuristic filter refine the candidate sot by removing the least common edges. Both steps are integral to the method. In this section, we explore what may be causing CPDAG-GFN to perform competitively compared to other baselines. First, examine the effect of the heuristic filter by comparing the top-K sampled CPDAGs before and after the filter is applied. Our results in Figure 22 show that applying the heuristic filter to the top-K samples from GFlow siguificantly reduces E-SHD, improving the aligument of the sampled graphs with the ground truth. This improvement allows CPDAG-GEN to achieve competitive performance against other baselines.
Next, natural question arises: CPDAG-GFN's competitive performance due to the heuristic filter alone (i.e., would applying the same filter to other baselines yield similar results?), does the filtering mechanism
23

---

Published in Transactions on Machine Learning Research (06/2025)
Dati,ionDaaa, ER-degl, noise-0.1
DutalionData, ER-degl, 0.1
aMillionData, ER-degl, noise-
1.00
30
0.95
E-SHD
AUROC
dislance
30
0.90
0.85
10
0.80
1445
D488
Dan
No 800
CYDAG-OR
B-065
DAG.ON
CHAG CMAG-aN
1080
DA0
CYDAG on
Figure 22: A comparison of baselines where filter applied and before is applied. Higher AUROC and lower E-SHD are preferred.
work particularly well when applied to the top-K samples from GFlowNet? To investigate this, we applied the heuristic filter to all baselines.
Our results in Figure 23 show that while the heuristic filter improves performance for the baselines, the improvement not as substantial as CPDAG-GEN. Specifically, while the heuristic filter leads some reduction in E-SHD for baselines like MC3, DAG-GFN, and DiBS, CPDAG-GFN, in particular, becomes more competitive with methods B-PC and B-GES after applying the filter.
MillionData, ER-degl, noise=0.1
Million obsData, ER-degl, noise=0.1
Million obsData, ER ER-degl, noise=0.1
1.00
0.95
E-SHD
AUROC
distance
30
20
0.90
0.85
0.80
0
8.N0
BeaEss
Mca
Mm3.
Dides
BAG-OON
DA6-OH
UPPAGEOE
BuPC
B a-00s
MC3+
Dins
DAG DAG-OEN
BaG-ONN-
OROAG-OEN
MC3
MCC
DAG DAG-GEN
Figure 23: A comparison of baselines where before heuristic filter is applied. Baselines with a plus sign (e.g.
blue box) indicate the application of heurisite filter, and green bax is without. Please note that wo-prior mcans CPDAG-GFN without houristic filter applied. Higher AUROC and lower E-SHD are preferred.
Possible reasons why the heuristic filter is less effective for other baselines:
Sampling Strategy: DAG-GEN, DiBS, and MC3 draw samples from learned posterior distribution and so are not guaranteed to always sample high-scoring graphs. As a result, their samples may still include a mix of high-, moderate-, and occasionally low-scoring graphs In contrast, CPDAG-GFN explicitly prioritizes high-scoring graphs by using GFlowNet
amortized sampler to sample the top K high-scoring CPDAGs. These top-K graphs tend to share common edges, many of which align with the ground truth. This structural consistency allows the heuristic filter to effectively refine the candidate set by removing the least common edges, thereby improving alignment with the true structure. However, when sampling does not explicitly prioritize high-scoring graphs but instead draws from a learned posterior distribution, the heuristic filter appears less effective Figure 23 reducing E-SHD compared to CPDAG-GFN.
Graphs already similar and close to ground truth: SenlstrrapingPPC/GGE have low distance shown in the distance plot. This suggests the sampled graphs are already similar to each other, and these graphs are in good alignment with the ground truth (as indicated by low E-SHD and high AUROC). Since these graphs already share a strong structural resemblance to the ground truth, the heuristic filter has limited room for refinement, resulting in less substantial improvement compared to CPDAG-GEN.
These experimental results demonstrate that the hcuristic filter alone insufficient achieve strong per- formance; CPDAG-GFN+ competitive performance arises from the synergy between using GFlowNet as an amortized sampler to sample top-K graphs and applying the heuristic filter.
24

---

Published in Transactions on Machine Learning Research (06/2025)
K Distinction Between the CPDAG-GFN and DAG-GFN Approaches
In this section, we highlight the key differences between CPDAG-GFN and DAG-GFN. While both methods use the GelowNet framework and have similar names, this is where the similarities end. Our approach diverges in several key aspects as outline below:
1. Different Learned Postcrior Distribution:
DAG-GEN uses GFlowNet to learn posterior distribution over DAGs, In contrast, CPDAG-GFN learns a posterior distribution over equivalence classes of DAGs (i.e., CPDAGs).
2. Different Use of the GFlowNeet Posterior:
DAG-GFN relies the learned posterior to produce set of candidate graphs where the samples are drawn at random from this distribution. As a result, the sampled graphs may span wide range of scores, including high-, moderate-, and low-scoring candidates. In contrast, CPDAG-GFN leverages the posterior as an amortized sampler, allowing the method to prioritize high-scoring graphs.
3. Different Search Space and Action Space
DAG-GFN:
Operates in the space of DAGs, where the primary constraint is to avoid generating cycles when adding directed edges (i.e., the action space consists only of adding directed edges).
The action space consist of adding directed edges, adding undirected edges, and creating v-structures ("makeV"). Each valid action must satisfy all four properties outlined in The- orem of our paper. As result, CPDAG-GFlownet must account for additional structural rules beyond simple cycle prevention.
CPDAG-GFN:
4. Different Neural Network Architecture
The graph neural network architecture of DAG-GFN, which handles only directed edges, employs a linear transformer. While efficient, the linear transformer may limit its capacity to capture complex, non-linear dependencies in observational data.
In contrast, we used Relational Graph Convolutional Network (RGCN) (see section 3.2.3). Our choice of RGCN allows to effectively model all three edge types (undirected, directed, and structures) in CPDAGs, capturing more complex relationship and structural properties in the data. This makes our implementation fundamentally different from that of DAG-GEN.
Additionally, our decoder differs from that of DAG-GEN. We use SimplE, which we found provides better performance compared the decoder used in DAG-GFN.
5. Heuristic Filter Our method introduces a heuristic filter that improves the quality of the sampled CPDAGs. This component absent in DAG-GEN, where only a uniform prior is used. We found that relying solely on uniform prior was not sufficient for producing competitive results in our experimental settings, motivating the development of the filter.
25

---

Published in Transactions on Machine Learning Research (06/2025)
L
Results for CPDAG-GFN on Larger Networks (20 and 50 Variables)
Results for d 20 variables
100 ohsiaat, ER-deg2, noise=0.1
obsData, ER-deg2, noise=0.1
100 obs ER-deg2, noise-0.
75
E-SHD
AUROC
60
0.72
45
0.64
30
B-PC
B-GES
DiBS
MC3
DAG-GFN
CPDAG-GFN
B-PC
B-GES
DiBS
MCa
DAG-GFN
CPDAG-GFN
B-PC
B-GES
DiBS
MC
DAG-GFN
CPDAG-GFN
Figure 24: Comparison of E-SHD and AUROC metrics on dataset with 100 observations, generated using ground truth graphs sampled from an Brdös-Réuy. (ER-deg2) model with noise level of 0.1. Lower E-SHD and higher AUROC preferred. A higher distance in the third figure indicates greater dissimilarity among the graphs
Results for 50 variables
100 obs Data, ER-deg2, 0.i
100 obsDala, ER-deg2, noise-0.1
100 Dafa, ER-deg2, noise- 0.1
0.9
200
180
F-SHD
150
AUROC
distance
160
0.7
120
120
0.6
0.5
B-PC
R-OES
DiBS
MC²
DAG-GFN
CPDAG-GFN
B-PC
B-OES
DiBS
MC²
DAG-GFN
CDDAG-GFN
B-PC
B-GES
DIBS
MC²
DAG-GFN
CPDAG-GFN
Figure 25: Comparison of E-SHD and AUROC metrics on dataset with 100 observations, generated using ground truth graphs sampled from an Erdös Rényi (ER-deg2) model with noise level of 0.1. Lower E-SHD and higher AUROC preferred. A higher distance in the third figure indicates greater dissimilarity among the graphs.
Erdös-Rényi
26

---

Published in Transactions on Machine Learning Research (06/2025)
Runtime trend in logscale
GES MC DBBS DIAKUTN
10"
Runtime (minutes)
10º
10a
10
10
10
20
30
40
50
of variables
Figure 26: Runtime trends in log-scale with 100 observational samples, noise level 0.1, and EPN.
M Runtime trend
We report the runtime trend for each method in Figure 26 All experiments Pro CPU (12 cores) with 24GB unified memory. As expected, bootstrapped PC and bootstrapped GES run fastest: although bootstrapping adds resampling overhead, the underlying PC and GES procedures are point-estimate methods, which are inherently faster than Bayesian approaches. CPDAG-GFN runs slower than DiBS and MCS, primarily due to the overhead training a generative flow network. While our method traverses CPDAG space, this factor alone does not explain the slowdown as shown by the fast runtime of bootstrapped GES, which also operates in the CPDAG space.
Apple M4
A second factor is that current implementation has not been optimized for runtime efficiency, as this lies outside the scope of the present work; however, this does not affect the methodological contribution of the work. Importantly, the obscrved trends align with expectations across basclines: bootstrapped point- estimate methods are faster, while Bayesian approaches trade speed for posterior modeling. We also note that GFlowNets represent different class of learning- based methods whose cost may amortize as problem complexity and scale increase, which may offer more favorable scalability in larger domains.
N Qualitative analysis of BayesDAG and BCDNets
In this section, provide qualitative comparison between two recent methods in Bayesian causal discovery: BCDNets and DAG.
In 2021, Cundy et al. 2021 proposed Bayesian Causal Discovery Nets (BCDNets), variational inference framework for estimating distribution over DAGs that characterize a lincar-Gaussian structural equation model (SEM). key strength of BCDNets lies in its of expressive variational family of factorized posterior distributions over the SEM parameters and continuous relaxations for optimization, enabling scal- ability to high-dimensional settings Cundy et al. (2021). One of the drawbacks with their method is their strong assumption that the true data-gencrating process follows a lincar-Gaussan SEM. While this assump- tion is common in causal discovery, the true data-generating process may not always follow a linear-Gaan Gaussian SEM in practice, constituting a strong modeling assumption that may limit the applicability of BCDNets in settings where the underlying process deviates from Gaussinn SEM. In contrast, CPDAG-GFN avoids assuming a specific functional form for the data-generating process and learns a distribution over equivalence classes of graphs (CPDAGs), which enables direct. sampling of CPDAGs.
27

---

Published in Transactions on Machine Learning Research (06/2025)
The second drawback of BCDNets is that it relies solely on variational inference, which may lead to promised inference accuracy (Annadani et al. 2023) In response to this limitation and the one mentioned above, Annadani et al. (2023) introduced BayesDAG, a scalable Bayesian causal discovery framework that combines stochastic gradient Markov Chain Monte Carlo (SG-MCMC) and variational inference (VI) to enable sampling directly from the posterior distribution over DAGs. One key strength of BayesDAG its applicability not only to linear causal relationships but also to nonlinear ones. This gives BayesDAG greater flexibility than BCDNets when modeling datasets where linearity assumptions may not hold.
Experimental results from Experimental results from Annadani et al. (023) show that BCDNets performs competitively with BayesDAG on Erdos-Rényi graphs, and outperforms BayesDAG on scale-free graphs under Gaussin data settings for a small variable space of d-5. This raises the question of how the performances of these two methods compare when scaling to larger variable spaces.
Although BayesDAG aims to improve inference quality by combining SG-MCMC and VI, this design choice raises questions about the computational complexity and potential trade-offs compared to purely variational methods like BCDNets in linear data settings. Specifically, while BCDNets may introduce inference errors due to its reliance variational inference alone, BayesDAG's use of SG-MCMC may present challenges commonly associated with MCMC methods, such as slow mixing and uncertainty in determining convergence. In practice, assessing convergence can be difficult, and early samples may bias the inferred causal structures. Nonetheless, BayesDAG demonstrates a clear advantage over BCDNets on nonlinear synthetic datasets, highlighting its greater flexibility modeling more complex causal relationships.
28


Reviews:
[{"review_id": "99lscZ4CuX", "reviewer": "Reviewer_naA1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### **Strengths**\n\n- The paper presents a fresh integration of GFlowNets into causal discovery by learning CPDAGs directly, which is timely given the rising interest in GFlowNet methods.\n- Working in CPDAG space eliminates the need to convert sampled DAGs into CPDAGs, focusing the sampler on equivalence classes and improving efficiency.\n\n### **Weaknesses**\n\n- As GFlowNets may be unfamiliar to some readers, it would help to include a boxed “Algorithm” in the main text that lays out the full CPDAG-GFN procedure in a single, coherent framework.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces CPDAG-GFN, a novel algorithm that directly samples Completed Partially Directed Acyclic Graphs (CPDAGs) using Generative Flow Networks. By operating in CPDAG space rather than DAG space, the method efficiently generates multiple high-scoring equivalence-class candidates without the extra conversion step.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In Section 3.2.1, “… ensuring that the graph resulting from any permitted action will also be a CDPAG.” Should read “CPDAG.”\n- As suggested in previous reviews, please add a brief paragraph on differentiable DAG learning methods (e.g., NOTEARS) and move the corresponding experimental comparisons into the main text.\n- Figure 3 nicely illustrates the CPDAG construction process, but it remains unclear how transitions between states are chosen. Are actions sampled via the learned forward policy, weighted by reward, or exhaustively enumerated? Please elaborate on the mechanism and whether all feasible actions are considered at each step.\n- The paper argues that “relying on the score to prioritize graphs may lead to discrepancies with the ground truth.” However, score-based DAG learning typically assumes that the true DAG obtains the highest score under a correct scoring function. Could the authors clarify why, in this setting, a high score might diverge from the ground truth?", "broader_impact_concerns": "Na", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "naz9EKjPMn", "reviewer": "Reviewer_MSdv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths:\n\n- The authors propose a principled and well-motivated approach that directly samples CPDAGs rather than DAGs, addressing the core challenge that causal discovery from observational data is only identifiable up to a Markov Equivalence Class (MEC). This design decision avoids unnecessary conversions and leads to a more faithful exploration of the relevant search space.\n- The paper proves that the selected set of actions (add directed/undirected edge, make-v) is sufficient to construct any valid CPDAG. This theoretical grounding strengthens the design of the search space and provides clarity on completeness.\n- The proposed filtering method for removing least-common edges among sampled CPDAGs is simple and effective. Empirical evidence shows that it leads to lower E-SHD and better alignment with ground truth, particularly when combined with GFlowNet’s top-K sampling.\n- Quantitatively, CPDAG-GFN outperforms or matches the best-performing baselines (e.g., DiBS, DAG-GFN, PC, GES) across most settings in terms of E-SHD, AUROC, and closeness to the correct number of edges.\n\n# Weaknesses\n\n- While the edge-sparsity heuristic works well empirically, it is not grounded in a formal Bayesian or statistical framework. The lack of theoretical understanding of when and why it works may limit its generalization to other domains or variants of the problem.\n- Although experiments are thorough, most settings are limited to 10-variable graphs. It would be helpful to see performance and runtime trends for higher-dimensional settings (e.g., 20–50 variables), which are more common in practical applications.\n- The model assumes a uniform prior over CPDAGs, which simplifies training but ignores the possibility of incorporating domain-specific structure priors. This could be particularly limiting in applications (e.g., genomics, medicine) where partial prior knowledge is available.\n- The evaluation focuses on graph recovery metrics (E-SHD, AUROC), but does not assess downstream causal tasks such as interventional prediction or counterfactual reasoning. It would strengthen the paper to include at least one such experiment.\n- The authors missed to compare with baselines such as or BCDNets [2021] or BayesDAG [ 2023]\n- This work uses E-SHD although a more suitable metric exist that evaluates CPDAGs (E-CPDAG SHD) (see \"Challenges and considerations in the evaluation of Bayesian causal discovery” and “BayesDAG: Gradient-Based Posterior Inference for Causal Discovery”)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work introduces a model for modeling a posterior distribution over the completed partially directed acyclic graph (CPDAGs) given observational data. To achieve this, the paper builds on GflowNets to learn a model that uses graph actions to sample the CPDAG sequentially. The authors introduce a sample based edge filter that removes the least common edges, which improves performance of the method by removing spurious edges. The method is evaluated on both synthetic datasets (across varying sample sizes, noise levels, and graph topologies) and a real-world protein signaling dataset (Sachs et al., 2005). Results are reported using the Expected Structural Hamming Distance (E-SHD), AUROC, and edge count. CPDAG-GFN performs competitively with, and in many cases outperforms, state-of-the-art baselines including DAG-GFN, DiBS, and MCMC-based methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- All experiments are performed on relatively small graphs with 10 variables. It is unclear how CPDAG-GFN scales to more realistic settings. The authors should provide either a larger study (50-100) or a justification of what are the scalability issues (lack of convergence or runtime / memory issues?).\n- I would like the authors to assess the E-CPDAG SHD as it’s more suitable for the task.\n- While the method is compared to strong baselines such as DAG-GFN, DiBS, and MC3, it omits evaluation against BayesDAG and BCDNets, which are recent and competitive Bayesian approaches to structure learning. These methods have shown strong empirical performance in both low- and high-dimensional settings. A comparison—either empirical or in-depth qualitative—would help better position CPDAG-GFN in the current landscape of causal discovery algorithms.\n- Figure 4 titles have some issues (e.g. aMillionData vs a Million obs Data - please unify)", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xmwlrNEdXz", "reviewer": "Reviewer_tz9G", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength:**\n\nThe structure learning of Bayesian networks (up to their equivalence class) is an important problem in machine learning. Rather than learning a posterior over DAGs directly, the authors propose a method that uses GFlowNet to learn a posterior over CPDAGs. The two important contributions come in terms of a) yielding Top-$K$ scoring CPDAGs and b) proposing a new filtering heuristic. The paper is generally well-written and conveys its ideas clearly.\n\n**Weaknesses:**\n\n1. The paper borrows heavily from the work by Deleu et al. (2022), adopting the key idea of employing GFlowNet while introducing modifications such as utilizing a state space of CPDAGs instead of DAGs and incorporating a Top-K approach with filtering. However, the authors could strengthen their contribution by clearly delineating other technical distinctions from Deleu et al. (2022) and elaborating on the specific technical challenges encountered in adapting and extending these methods to their proposed setup.\n2. Given the limited technical novelty, the primary value of the paper could have been demonstrated through superior performance against existing baselines across a diverse range of examples or performance metrics. Unfortunately, the numerical results presented are only competitive, with performance varying across different metrics. Notably, some of the most intriguing aspects of the paper are relegated to the Appendix (specifically sections D, E, F, H, I, and J). Upon reviewing the provided figures, it appears that DAG-GFN from Deleu et al. (2022), when equipped with Top-K sampling and filtering heuristics, performs comparably to the proposed method. \n3. I am unclear about the process for selecting hyperparameters such as K and L. While Appendix E outlines an approach for choosing L, it is not evident whether the suggested range of 30–40 for L would remain valid across Bayesian networks with differing numbers of nodes or edges. Authors should also specify these numbers in the experiments they reported.\n4. It would be a good addition to have experiments showing whether the proposed method scales with the number of nodes/edges in the Bayesian networks. Authors should clearly specify these numbers in the experiments they reported.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors address the problem of learning equivalence classes of Bayesian network structures from observational data using Generative Flow Networks (GFlowNets). Their approach involves learning a posterior distribution over Completed Partially Directed Acyclic Graphs (CPDAGs) and identifying an optimal set of $K$ candidates that achieve the highest scores from the amortized sampling. To refine the results, the authors perform postprocessing by removing the least common edges among the sampled graphs. The proposed GFlowNet framework includes a state space represented by CPDAGs, a reward function, and a parameterization with graph neural networks. The authors validate their method through numerical experiments conducted on both real and synthetic datasets, demonstrating its applicability and effectiveness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the previous section. Additionally, I also sighted a few minor writing issues in the paper:\n1. I could not find the definition of the abbreviation MLP used on page 6.\n2. I suspect that DAG-GFlowNet and DAG-GFN are used interchangeably on page 2.\n3. In Figure 8, DAG+ is perhaps used to denote the use of the filter. However, this is not made clear in the text.\n4. Appendix E has a missing Figure reference in line 3.\n5. Figure 22 has repeated labels (y-axis) for two of the figures.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)