Differentiable DAG Sampling
Authors: Bertrand Charpentier
Simon Kibler
Stephan Günnemann
Venue: ICLR 2022 Poster (2022)
Keywords: DAG
Differentiable
Sampling
Probabilistic model

Abstract: We propose a new differentiable probabilistic model over DAGs (DP-DAG). DP-DAG allows fast and differentiable DAG sampling suited to continuous optimization. To this end, DP-DAG samples a DAG by successively (1) sampling a linear ordering of the node and (2) sampling edges consistent with the sampled linear ordering. We further propose VI-DP-DAG, a new method for DAG learning from observational data which combines DP-DAG with variational inference. Hence,VI-DP-DAG approximates the posterior probability over DAG edges given the observed data. VI-DP-DAG is guaranteed to output a valid DAG at any time during training and does not require any complex augmented Lagrangian optimization scheme in contrast to existing differentiable DAG learning approaches. In our extensive experiments, we compare VI-DP-DAG to other differentiable DAG learning baselines on synthetic and real datasets. VI-DP-DAG significantly improves DAG structure and causal mechanism learning while training faster than competitors.

Published as a conference paper at ICLR 2022
DIFFERENTIABLE DAG SAMPLING
Bertrand Charpentier, Simon Kibler, Stephan Günnemann Department of Informatics & Munich Data Science Institute Technical University Munich (charpent, kibler, guennemann @iin tum. de
ABSTRACT
We propose new differentiable probabilistic model over DAGs (DP-DAG). DP- DAG allows fast and differentiable DAG sampling suited to continuous optimiza- tion. To this end, DP-DAG samples DAG by successively (1) sampling linear ordering the node and (2) sampling edges consistent with the sampled linear ordering. We further propose VI-DP-DAG, a new method for DAG learning from observational data which combines DP-DAG with variational inference. Hence, VI-DP-DAG approximates the posterior probability over DAG edges given the observed data. VI-DP-DAG is guaranteed to output a valid DAG at any time during training and does not require any complex augmented Lagrangian optimization scheme in contrast to existing differentiable DAG learning approaches. In our ex- tensive experiments, we compare VI-DP-DAG to other differentiable DAG learning baselines on synthetic and real datasets. VI-DP-DAG significantly improves DAG structure and causal mechanism learning while training faster than competitors.
INTRODUCTION
Directed Acyelic Graphs (DAGs) are important mathematical objects in many machine learning tasks. For example, direct application of DAGs is to represent causal relationships in system of variables. In this case, variables are represented as nodes and causal relationships are represented as directed edges. Hence, DAG learning has found many applications for causal discovery in biology, economies or planning (Pearl 1988 Ramsey et al., 2017; Sachs et al., 2005 Zhang et al. 2013) However, challenging problem two reasons. First, while DAG learning with data from randomized and controlled experiments is the gold-stane gold-standard for causal discovery, experimental data might be hard or unethical obtain in practice. Hence, a more common but also challenging setting DAG learning from observational data which is possible under proper conditions (Pearl, 2009) SSpirtes) jt al. 2000). Second, the number of possible DAGs scales nuper-exponentially with the number of variables which makes DAG learning an NP hard problem (Chickering et al. 2012 Robinson 1973).
DAG learning
first traditional family of models for DAG learning are discrete score-based approaches. These approaches aim at solving the following discrete optimization problem:
max (xcoreX,c0m G) G discrete DAGS
where X denotes the observed data and the discrete DAGs space is composed of DAGs with un- weighted (present or absent) edges. Examples of score functions are Bayesian Information Criteria (BIC) (Chickering & Heckerman 1997) or Minimum Description Length (MDL) (Bouckaert, 1993). Discrete approaches have two main limitations: (1) the optimization search space of discrete DAGs large and constrained which often makes the problem intractable without further assumptions, and (2) the learning procedure is not differentiable and thus not amenable to gradient-basse
optimization,
as done by most deep learning approaches. To mitigate these issues, second more recent family of models for DAG learning proposes to leverage continuous optimization by using an augmented Lagrangian formulation (Lachapelle al.) 2020 Ng et al., 2019; Wehenkel & Louppe| 1021 Yu
ct al. 2019 Zheng et al. 2018). These approaches aim at solving the following optimization problem:
max Score(X, G) s.t. h(G) = 0
(2)
where (G) is smooth function over weighted graphs G which is equal to zero when the graph G satisfies the DAG constraints. Standard examples of score functions (negative) cross-entropy (Yu

---

Published as a conference paper at ICLR 2022
Permutation Matrix
Edge Matrix
Adjacency Matrix
121
T- (.)
UnPa (U)
D'Un
Figure 1: Overview of differentiable DAG sampling.
et al. 2019) or Mean Squared Error (MSE) (Ng et al. 2019) when reconstructing the data. During optimization, G is a weighted graph where the discreteness and acyclicity constraints are relaxed. Hence, these continuous optimization approaches have two main limitations: (1) the augmented Lagrangian optimization computationally expensive as it requires multiple complex dual ascent iterations, and (2) the discrete and acyclicity constraints relaxed during optimization which does not guarantee valid discrete DAGs without non -in-differentiabee pre- and post-processing as proposed by Causal Additive Model (CAM) (Bühlmann al.) 2014). For more comprehensive description, we recall the augmented Lagrangian optimization method in detail in App.
In this paper, focus on differentiable DAG learning methods and make the following contributions:
We propose new probabilistic model over DAGs (DP-DAG) which is capable of fast and differentiable sampling. DP-DAG can be implemented few lines code using Gumbel- Sinkhorn, Gumbel-Top- and Gumbel-Softmax distributions to parametrize differentiable sampling over permutations and edges (see Fig. T and F
We propose a new method for DAG learning from observational data (VI-DP-DAG) which in- stantiates general probabilistic formulation for DAG learning with DP-DAG and variational inference. VI-DP-DAG guarantees valid DAG outputs at any time during training.
We show in our experiments on established synthetic and real datasets that DP-DAG outperforms other differentiable DAG learning baselines for DAG structure and causal mechanisms learning while training one order of magnitude faster.
2
RELATED WORK
We differentiate between three types of DAG learning approaches: the discrete optimization ap- proaches, the continuous optimization approaches and the sampling-basee approaches. We refer to the survey (Vowels et al. 202T for more detailed overview of DAG learning approaches.
Discrete optimization. First, to make the search space more tractable, discrete optimization ap- proaches modify the original problem with additional assumptions on DAG treewidth (Nie et al. 2014 Scanagatta et al. (2116). ancestral constraints (Chen et al. 2016) or on the number of parents of each variable (Vinikka al., 2020). Other methods based greedy search (Chickering 2002)
discrete optimization of the topological order (Park & Klabjan 2017] Scanagatta et al., 2013 Teyssier
Koller, 2005). Another type of discrete optimization approaches are constraint-basee methods.
These methods explore the discrete DAG space by performing independence tests between observed variables (Bhhlmann et al. 2014 Spirtes et al. (00TT.
Continuous optimization. Second, continuous approaches usually relax the discreteness and acyclicity constraints by using an augmented Lagrangian formulation of the optimization prob- lem (Lachapelle et al. 2020; Ng et al. 2019 Wehenkel & Louppe, [02T] Yu et al.) 2019 Zheng et al. 2018). Some approaches deñne the DAG structure from neural network weights (Lachapelle et al.
2020 Zheng et al.,, 2018) while other approaches directly learn the DAG adjacency matrix (Ng et al.
2019 Wehenkel & Louppe, 2021 Yu et al. 2019). In contrast to these methods. VI-DP-DAG learns probabilistic model over the DAG structure. Further, these approaches penalize DAG constraints violation in the augmented Lagrangian formulation but do not guarantee that they are fulfilled during training. Recently, Yu et al. (2021) propose to complement the augmented Lagrangian optimization with a second step projecting the learned graph on admissible solutions. Hence, contrary to VI-DP. DAG, most of these approaches non-differentiable processing steps e.g. removing cycles and
2

---

Published as a conference paper at ICLR 2022
spurious edges- to output valid and high-quality DAGs, Common examples of processing steps Preliminary Neighbors Selection (PNS) and CAM pruning (Bühlmann et al.) 2014).
Sampling-based optimization. Third, other works use DAG sampling to estimate the posterior distribution over DAGs with MCMC (Kuipers et al. 2020; Nimimāki et al.] 2011: 2016 Talvitic et al. 2020 Viinikka et al. 2020). While previous works improve the quality and speed of MCMC computations by sampling (partial) orders or making assumptions on the number of parents per node, they are still computationally extremely expensive (Kuipers et al. 2020; Nünimääi al.) 2011, 2016, Viinikka et al., 2020). Lig...Viiiikka el al. (2000) recommend to run MCMC methods during 12 hours to sample from the posterior distribution over DAGs with 100 nodes. In contrast, VI-DP-DAG approximates the posterior distribution over DAG edges with variational inference and can sample very fast. E.g., our VI-DP-DAG trains in around 190 seconds and samples in less than second for DAG with 100 nodes. Further, while the construction of the MCMC chains are generally non-differentiable, our DP-DAG is capable of fully differentiable DAG learning and can leverage gradient-bad based optimization. Other works propose optimization of discrete problems using differentiable probabilistic distribution over various discrete objects like subsets or spanning trees but not on DAG structures (Grathwohl et al. 2021 Karalias & Loukas 2020 Paulus al. 2020). Further, recent works combine differentiable edge sampling with Gumbel trick and Lagrangian optimization but do not define valid distributions over the full DAG structure (Brouillard al. 2020 Ng et al. 2019). In contrast, DP-DAG does not require complex Lagrangian optimization and guarantees valid DAGs solutions any time during training. Finally, Grosse et al. (202I) explores an orthogonal direction where the search space in sequential decision making problems is represented with DAG.
3 PROBABILISTIC MODEL OVER DAGS
A Directed Acyclic Graph (DAG) is a graph G = (V, E) with n nodes Ii,..., In and m directed edges which does not exhibit directed cycles. A DAG always admits valid permutation (or linear ordering) क: [L, n] + [1, ri] of the nodes such that a node cannot have a direct edge toward a node with lower rank i.e., (t)) T(j) implies no directed edge from node (x()) to node ( Valid permutations are often not unique. Interestingly, this property has an equivalent matrix formulation:
Theorem 1. Lets A (0, 1)ah be the (a priori non-triangular) adjacency matrix associated with an arbitrary node labelling of the DAG G. The adjacency matrix A always admits a permutation matrix II E {0, 1 and an upper triangular matrix U {0, 1]"Xn such that A II-UUI.
The permutation matrix II directly corresponds to a valid component-wise permutation л. Hence, Th. simply states that the matrix U is the new adjacency matrix where the new node labels are a valid permutation of the original node labels i.e. A.j = U (z))m()) such that U ()) = 0 if T (i) < T (z). The decomposition of the DAG adjacency matrix A in Th. 1 is generally not unique as DAG G generally admits multiple valid linear permutations IT. Hence, we define the following probabilistic model over DAGs (DP-DAG) based on the adjacency matrix decomposition in Th. [
P(A)= =
Σ
P(U) P(II) S.L. A UII
(3)
IEP((G).EU
where P(G) is the set of valid permutation matrices for the DAG G, Un is the space of binary upper-triangular matrices of size n x n, PIII) is the distribution over permutations and (UU) the distribution over edges consistent with the sampled permutation of the nodes. Note that the number of valid permutations [P(G) can be exponentially large in the number of nodes which makes the exact computation of the probability of a given DAG adjacency matrix P(A) intractable for large graphs. However, DAG sampling does not require any enumeration of the valid linear permutations. Indeed, we propose new differentiable DAG sampling method (i.e. A Po.v (A)) based on differentiable edge sampling (i.e. U ~ PU) and differentiable permutation sampling (i.e. II ~ (IT)). The variables vi and o denote the parameters of the edge and permutation distributions.
Differentiable edge sampling. The Bernoulli distribution is a well-suited distribution to model randomness over discrete binary variable like edge U1 E {0, 1 ~ Ber(p) where p E [0, 1] is the probability for the edge to exist. Unfortunately, standard random sampling operations from the Bemouuli distribution are not differentiable. In contrast, the Gumbel-Softmat distribution allows for differentiable sampling and approximates the Bernoulli distribution (Jang et al.) 2017). The Gumbel- HombbelSofftmx-1(e
Softmax distribution is defined continuous variables, i.e. Üi E (,,
3

---

Published as a conference paper at ICLR 2022
with o E [0. 1), where the temperature parameter allows to interpolate between one-hot-encoded categorical distribution (T - 0) and continuous categorical densities (T + +oo). For differentiable sampling, can the straight-throughe estimator (Bengio et al., 2013); we use the discrete variable Uy = arg max[1 - U. U,y] in the forward pass, and the continuous approximation Ulj in the backward pass. Thus, sampling all the upper triangular indices of U {0, 1)mx* has complexity Onn²). We recall the definition of the Gumbel-Softmax distribution in detail in App. B.1
Differentiable permutation sampling. Similarly to an edge, a permutation II is discrete, making differentiable sampling challenging. We describe two alternative methods which allow for differ- entiable permutation sampling. First, the Hombeel-Snnhoomm (Mena et al.) 2018) is defined on a continuous relaxation of the permutation matrix, i.c. II E [0, 1] 10 ~ GGumbel-Sinhoone (v) with v E [0, 1] | where the temperature parameter 7 also allows to interpolate between discrete and continuous distributions similarly to the Gumbel-SSofmax distribution. For differentiable sampling, we can use the atraight-through estimator (Bengio et al.) 2013): we use the discrete permutation
II Hungarian(1 [I] by applying the Hungarian algorithm (Munkres, 1957) to compute a discrete
permutation in the forward pass, and the continuous approximation II in the backward pass. Sampling a permutation matrix II {0, 1 jxx= is dominated by the Hungarian algorithm and has a complexity of On²*). We recall the definition of the Gumbel-Sinkhorn distribution in detail in App. B.2
A second method orthogonal to the Gumbel-SSnkhom method is to use the combination of the Gumbel-Topp trick (Kool et al. 2019) and the SoftSort operator (Prillo & Eisenschlos 2020) which also defines a distribution on a continuous relaxation of the permutation matrix. For n, the Gumbel- Top-n distribution states the sorted perturbed log-probabilities, i.e. я = Sort 1b + G') where parameters 1 are log- log-probabilities and G RR" are i.i.d. Gumbel noise, defines a distribution over component-wit wise permutation (a.k.a. linear ordering without replacement), Instead of the Sort oper- ator, we apply the SoftSort operator to the perturbed log-rrobaiilities which outputs a continuous relaxation of the permutattion matrix, i.e. II SoftSort 3b + G) E R"** For differentiable sam- pling. we use the straight-througe estimator (Bengio et al. 2013): we use the discrete permutation II arg max II by applying the (one-hot) argmax operator row- wise (Prillo & Eisenschlos) 2020) in the forward pass, and the continuous approximation II in the backward pass. Sampling a permutation matrix II (0, 1] |xx is dominated by the SoftSort operation and has complexity of O(n)).
The permutation sampling complexity with Gumbel-Top4 combined with SoftSort is thus lower than the permutation sampling complexity with Gumbel-Sinkhorn. We recall the definition of the Gumbel-Top-k distribution and SoftSort operator in detail in App. B.3 and App. C
Differentiable DAG sampling. Given the aforementioned methods for differentiable edge and permutation sampling, we propose new simple and valid sampling procedure for DAG sampling which consists in three steps (see Fig. D): (1) Sample a permutation II from a probabilistic model over permutations Pa (TT) i.e. II ~ st (IT). (2) Sample an upper triangular matrix U by sampling the upper triangular elements from a prohabilistic model over edges Pg(U.) i.e. Ug, ~ P (U,)) (3)
Compute the final adjacency matrix A from the permutation matrix II and the upper triangular matrix U.e. A = II UII. This procedure is capable of sampling any possible DAGs of n nodes because propose parametrize the distribution P. (IT) using the Gumbel-Sinkhorm
of Th. [ In practice, or the Toppb trick which define valid distributions over permutations, and parametrize the distributions P (U.g)) using the Gumbel-Softmax trick which defines valid distribution over edges. Given these parametrizations, the sampling procedure allowsfas and disferentiable sampling and can be implemented in a few lines of code (see Fig. 2). The total DAG sampling complexity is dominated by the permutation sampling step which has a complexity of O(n²) using Gumbel- Sinkhorn and (nn)) using Gumbel-Top- combined with SoftSort. Finally, the DAG sampling procedure of DP-DAG guarantees a valid DAG output at any time during training without additional pre- or post-prost post-processing steps.
der differentiable dag___gg__eeeeeeeeeeeeee (ae_f): * (1) Pi > P ((Pi) using Gunbel-Sinkhorn Gumbel Sombel-Top-2
Pi = sel...samlle.pemmtattt
Pi_inv P.cranspooe
5
a (2) 0 (() uaing Gunbel-Softmax dag_adj a (3) A PinT 1 P1 usiig Theorem
self.sample_edger (]
mask furch,,riu ceer
self.a_nodes), 1)
dag_adj dag_adj (2i_inv A mask B. Pi) return dag_adj
18
Figure 2: Differentiable DAG sampling in Python
4

---

Published as a conference paper at ICLR 2022
4 VARIATIONAL DAG LEARNING FROM OBSERVATIONAL DATA
Structural Equation Model (SEM). We assume that the data follow a SEM i.e. I;; = Si pe (s) ei) where Ej are independent noises and f is the ground-truth causal mechanism which deterministically transforms the parent causes paa" (x) and noise & in the consequence value 24. We assume that all variables are observed. We aim learning both the true parents pa" (i) for each node describing the direct cause- consequenee relationship, and the true causal mechanisms f Alternatively. SEM can equivalentl be written in a matrix form. Indeed, one can use the DAG adjacency matrix A
as a mask before applying the causal mechanism S i.e. X, = (A; (A X, e:). Similar masking formulations of a SEM have been used in previous works (Brouillard et al. 2020 Ng et al. 2019).
Probabilistic DAG learning loss. We propose new general formulation for DAG learning based on diffcrentiable DAG sampling which intuitively aims at maximizing the expected score Eg Ca[score(X, G)] under the probability distribution over DAGs Pa.p(G) i.e.:
max Ealscore(X, (xtcoore(X,)))))) G)] s.t. G Po.. (G) $..0
(4)
This formulation allows a rich probabilistic solution that assigns a confidence score to all possible DAGs. In contrast, the discrete and continuous DAG learning formulations in Eq. | and Eq. 2 only compute a single point estimate DAG solution and do not model any uncertainty on the final DAG output. specific instance of the Eq.
4 4is the optimization of the following ELBO loss:
max L FAMP aA (oxg (x) -AKL( a. (A)ll prior (A)) 0,0,0
(5)
(i)
where À E RR+ is a regularization factor and 0, Φ, s/ are the parameters of the model to optimize. Indeed, similarly to Eq. 4 both terms (i) and (ii) can be formulated as an expectation over the DAG probabilistic model P (A). Importantly, the optimum of the variational inference problem in Eq. 5 is reached when the learned probability distribution over DAGs is equal to the posterior probability distribution over DAGs i.e. P(A Φ, v)) z (D) where 'D denotes the dataset of observations.
Variational inference with DP-DAG. We propose VI-DP-DAG, a new method combining DP-DAG and variational inference to learn the matrix form of SEM from observational data. At training time, VI-DP-DAG consists of three steps: (1) It differentiably samples a valid DAG adjacency matrix A from a probabilistic model over DAGs P P.. (A). In practice, we parametrize P Po.y( (A) with DP-DAG. (2) It applies the n transformations fú, on the observations X masked with the sampled DAG A i.c. X, (A, o X, G.). In practice, we parametrize fú, with neural networks. (3) It jointly updates all parameters 0, Φ, 16 by maximizing at each iteration an approximation of the ELBO loss in Eq. 5 In practice, we approximate the term (i) by sampling a single DAG matrix A each iteration and assume
a Gaussian distribution with unit variance around X (i.e. (i) = ||X X||2). We compute the term (ii) by setting small prior P (rtee(Us) (Uay) on the edge probability (i.e. (ii)= Enj (L (Us)) P Pptrr (Ug)) ) thus acting as a natural sparsity regularization. We set no prior on the permutation probability for two reasons: In theory, a permutation prior is likely biased toward graphs that are compatible with larger number of orderings (Kuipers & Moffa, 2017 Viinikka et al., 2020). In practice, the closed-fone computation of the permutation probability Po ( (II) is generally intractable (Mena et al. 2018). Thus, VI-DP-DAG approximates the true posterior distribution over DAG edges probability only. which achieves excellent predictive performance in practice. Beyond variational inference, VI-DP-DAG is theoretically motivated from a second perspective. Assuming that the data comes from SEM with additive noise, Ngg et al. (2019) showed that minimizing the term (i) enforces the sampled matrix A to represent super-graph of the ground-truth DAG adjacency matrix A (i.e. all the edges in A x are also in A) thus suggesting to add a sparsity regularization term to remove spurious edges. Interestingly, the term (ii) which arises naturally from the variational inference framework indeed acts a sparsity regularizer and pushes the probability PP Po to the fixed low prior value (U)))(U1;)))
At inference time, we can use VI-DP-DAG in two ways. On one hand, we can extract the cause/conse- quence relationships from, e.g., one sampled DAG adjacency matrix A. On the other hand, we can esti- mate the missing values x; from its learned parents and causal mechanisms i.c. F, Rs f. = fro (x (I)p())). Intuitively, a small prediction error ||2, & indicates that the learned parents xpa forecast well the child node x; i.e. the parent nodes (1a(1) are Granger-causes of the child node 27;
5

---

Published as a conference paper at ICLR 2022
5 EXPERIMENTS
In this section, we compare VI-DP-DAG to existing methods for differentiable DAG learning on extensive experiments including undirected and directed link prediction, consequence prediction from learned causal mechanisms, and training time. This set-up aims at highlighting the speed and quality of VI-DP-DAG for DAG structure learning and causal mechanisms learning. Further, we evaluate the speed and the optimization quality of the probabilistic model DP-DAG alone.
5.1 SET-UP
In our experiments, VI-DP-DAG parametrizes the permutation probability (IT( with Gumbel- Sinkhorn or Gumbel-Top-k trick, the edge probability (U) with Gumbel-Softmax distribution and the causal mechanisms fi.e with a 3 layers Multi-Layer Perceptron (MLP). We use early stopping and perform grid search over the permutation probability parametrization (i.e. Gumbel-Top-k). the fixed prior probability P (Ui)) [le [le-2, 1]= and the regularization factor X E [0, ). Finally, all temperature parameters are fixed to r = 1 in all experiments.
or
Baselines. We focus our evaluation on differentiable methods for DAG learning and compared to DAG-GNN (Yu et al. 2019)), DAG-NF (Wehenkel& & Louppe 2021), GraN-DAG (Lachapelle et al.) 2020) and Masked DAG (Ng et al., 2019) by using their official implementation when available. Unless otherwise stated, we did not use non-differentiable pre- or post-processing steps for any of the models. For the sake of completeness, we also compare DP-DAG with models using non- differentiable pre- and post-processing like Preliminary Neighbor Selection (PNS) and CAM pruning (Bühlmann et al. 2014) in App. F33 Similarly to VI-DP-DAG, we perform a grid-search for the hyper-parameters of all models (including learning rate, number of hidden units per linear layer, or regularization factors). For all metrics, we report the mean and the standard error of the mean of the results over 10 runs. We give further details on the models in App.
Datasets. We use a total of 11 synthetic and real datasets. For the synthetic datasets, we closely follow (Lachapelle et al., 2020 Ng et al., 2019 Peters al.] 2014). The graph structures A' were generated with the Erdös-Rényi Rényi (ER) or Scale-Frec (SF) network models, and the causal mechanisms fi were generated from (non-linear) Gaussian Process with RBF kernel of bandwidth one and with independent zero-mean Gaussian noises We considered different sizes of graphs including number of nodes n in {10, 50, 100) and number of edges m in (10, 40, 50, 100, 200, 400). We denote the synthetic datasets by SF/ER-n-m.. We used 10 sampled datasets per setting. For the real datasets, we closely follow (Koller& & Friedman] 2009; Lachapelle et al. 2020 Ng et al.) 2019; Yu al.) 2021 Zheng al. 2018). We use the Sachs dataset which measures the expression level of different proteins and phospholipids in human cells (Sachs et al., 22055.. We also use the pseudo-real SynTReN dataset sampled from generator that was designed to create synthetic transcriptional regulatory networks and produces simulated gene expression data that approximates experimental data (Van den Bulcke al., 2006). For all these datasets,
access the ground-truth DAG adjacency matrices A used to generate the data or estimated by experts. We split all datasets in training/validationn validation/tess sets with 40%% 1000%. 10%. We give further details on the datasets in Sec. Dji the appendix.
5.2 RESULTS
DAG sampling. We show results for the DAG sampling time in Fig. 3 and Fig. 4in the appendix. While both Gumbel Sinkhorn and Gumbel-Top-k parametrizations can sample DAG with 200 nodes in less than 1 second, Gumbel-Top-k is significantly faster than Gumbel--Snnkhon as expected from the complexity analysis. Further, we show the results of differentiable sam- pling optimization using DP-DAG for DAG learning when the ground-truth DAG is observed in Tab. Glin the appendix. On this
Sampling time (seconds)
Humbel-Sinkhore
Gumbel-Top-k
0.2
0.0
toy task, DP-DAG recovers almost perfectly the ground-trumt -rruh DAG structure. These observations validate that DP-DAG is a reliable method for fast and differentiable DAG sampling. Further details about these experiments are in App. F.
50
150
200
Number of nodes
Figure 3: Sampling time of DP-
DAG using Guumbel-Sinkhorn or Gumbel-Top-k.

---

Published as a conference paper at ICLR 2022
DAG structure. We evaluate the learning of the DAG structure by comparing the ground-truth adjacency matrix A to the learned score S.y. For baselines, we use entries from the weighted adjacency matrix Sij Ai as scores for directed edges, and Siy undirected edges. For DP-DAG, we use the edge probability Sij = Pe Aij + Aje scores for (U(Un(()(())) as scores for directed edges and S = ()((U(()())) + P)((Uz()7(1)) as scores for undirected edges. In this case, the permutation π (or equivalently II) is deterministically computed by removing Gumbel noise in the forward sampling step. The directed scores (Dir-) indicate if an edge with a specific direction exists between two nodes. The undirected scores (Un-) indicates if an edge without specific direction exists between two nodes. We compare the directed and undirected scores to the ground-truth binary adjacency matrix by using the area under the curve of precision-reeall (AUC-PR) and the area under the receiver operating characteristic curve (AUC-ROC). These metrics have the important advantage to be independent of a threshold choice (Vowels al., 202T). Thus, AUC-PR and AUC-ROP are better indicators of the true performance of the models contrary to other structure metries like Structural Hamming Distance which needs to arbitrary select threshold.
We show the results for differentiable DAG structure learning on synthetic and real datasets in Tab. and in Tab. in the appendix. total, VI-DP-DAG achieves 27/44 best scores and second-best scores otherwise. On synthetic datasets, only GraN-DAG competes with VI-DP-DAG on small datasets with 10 nodes. DP-DAG outperforms all baselines on all larger synthetic datasets with 50 or 100 nodes for both ER and SF graph types. E.g. the ER-100-400 dataset, VI-DP-DAS -AG gives an absolute improvement of +17% for Un-AUC-PR, +25% for Un-AUC-ROC, + +33 for Dir-AUC-PR and +9% for Dir-AUC-ROC. We observe that DAG-GNN and DAG-NF perform comparably random guessing corresponding to an AUC-ROC of 50% on those datasets. We hypothesize that their poor performances might be due their incorrect modeling assumptions or their incapacity to model this type of causal relationships as mentioned in Lachapelle et al. (2000) Yu et al. (2019). On real datasets, no baseline consistently outperforms VI-DP-DAG which obtains 4/8 best scores and second-best scores otherwise. We observe on both synthetic and real datasets that VI-DP-DAG performs better with undirected edges scores than with directed edges scores indicating that VI-DP-DAG might invert the edge directions. This can be intuitively explained by the presence of node pairs where v; is an equally good predictor of i as Ty is good predictor of x;. Finally, we show further evidence that VI-DP-DAG learns reliable DAG structures under perturbations in App. F.5 Indeed it confidently assigns lower confidence scores to perturbed versions of the ground-truth DAG.
We show the results for DAG structure learning with non-differemtiable pre- and post-processing in Tab. [ and Tab, in the appendix. In these experiments, we apply the default pre- processing PNS and post-processing CAM pruning steps to CAM (Bühlmann et al. 2014), GraN-DAG (Lachapelle et al. 2020), Masked-DAG (Ng et al., 2019) as suggested by the original papers. We similarly apply CAM pruning the final results of VI-DP-DAG. In this case, we observe that the greedy CAM is the best performing model for most synthetic datasets while VI-DP-DAG maintains competitive performance. Interestingly, VI-DP-DAG with non-differentiable pre- and post-processing is the best performing model on real datasets (i.e. 7/8 best scores). Further, we notice that the pre- and post-processing steps raise significantly the scores of GraN-DAG and Masked-DAG which becomes more competitive with VI-DP-DAG, while VI-DP-DAG benefits from it to lower extent (e.g. see ER-100-40K in Tab. and Tab. K. This suggests that methods based on augmented Lagrangian optimization are more dependent on additional nin-differeetiable processing steps than VI-DP- Laacaalaaaaplleeeee et al. (2020) make similar observations on the dependence on PNS and CAM pruning steps.
Causal mechanisms. We evaluate the causal mechanisms learning by computing the Mean Squared Error (MSE) between the ground-truth node values x; and the estimated node values é; = [ (i)) on new test set. It can be computed in vectorized way i.c. ||X - -X113 where X, = f X). This task is particularly important when predicting missing values from the values of known parent causes. For this experiment, we compare to other baselines which jointly learn the adjacency matrix A and the causal mechanisms fi, explicitly. Hence, we compare to Masked-DAG and GraN-DAG. At testing time, we remove the remaining cycles from the adjacency matrix A learned with augmented Lagrangian optimization to guarantee a valid DAG structure as suggested by Lachapelle et al. (202)); Ng et al. (2019). Further, we also compare to GT-DAG which uses the ground-truth DAG adjacency matrix A at training and testing time. GT-DAG can be considered as lower bound for the MSE scores. It indicates if other methods manage to jointly learn well both the DAG structure A and the causal mechanisms fi... For DP-DAG, the adjacency matrix A is computed by deterministically computing a (or equivalently IT) without Gumbel noise in the forward sampling step, and second
7

---

Published as a conference paper at ICLR 2022
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
DAG-GNN
18.67 = 0.17
48.44
8.21
47.83 + 0.34
DAG-NE
16.11 + 0.12
50.20 + 0.03
+.15+0077
50.19 + 0.02
GraN-DAG
25.11 + 0.4
56.57 + 0.35
17.61 0.47
56.35 + 0.34
Masked-DAG
17.55 + 0.14
51.09 + 0.05
9.14
50.81 + 0.04
VI-DP-DAG
62.08 0.34
84.53 + 0.25
41.70 0.39
71.08 + 0.33
ER-50-200
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
DAG-GNN
1.65=0.2
49.05 0.2
5.56
47.47
DAG-NE
7.82
49.98 0.02
3.94
50.05 0.02
GraN-DAG
9.73
5.11
4.02
5.00
Masked-DAr
8.93 0.12
50.65 0.06
4.73
5.06
VI-DP-DAG
36.98 0.98
77.23 0.63
19.00 1.07
6
(b) BR-100-400
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
DAG-GNN
14.94 0.17
51.41 + 0.26
50.31 0.27
DAG-NF
11.83 0.1
50.18 0.03
5.86
00.02
GraN-DAG
18.75 = 0.29
54.76 0.17
12.35
53.31 1 0.43
Masked-DAG
14.39 = 0.13
51.64 0.06
7.23 0.12 0.12
50.97
0.06 0.06
VI-DP-DAG
33.81 + 0.39
68.18 - 0.39
17.46 0.34
59.70 + 0.65
(c) SF-50-200
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUCPPR
Dir-AUC-ROC
DAG-GNN
49.92 + 0.46
59.59 + 0.57
23.84 0.52
51.67 + 0.62
DAG-NE
35.66 + 0.32
53.57 + 0.44
15.43 +.43+00.1 0.11
50.16 + 0.31
GraN-DAG
34.28 + 0.32
54.57 + 0.36
19.95 + 0.35
55.91 + 0.33
Masked-DAG
36.98 + 0.25
55.13 + 0.15
17.74 0.31
51.71 0.23
VI-DP-DAG
43.37 = 0.55
59.78 + 0.62
22.96 0.81
60.02 + 0.91
(d) Sachs
Models
Un-AUC-PR
Un-AUC-ROC Dir-AUC-PR
Dir-AUC-ROC
DAG-GNN
24.83 + 0.19
66.75 + 0.2
+ 9.26+000
59.61 0.19
DAG-NF
12.89 0.15
49.02 + 0.24
6.63+0.15
49.11 + 0.16
GraN-DAG
19.89 + 0.4
62.29 + 0.31
15.39 0.44
63.91 + 0.34
Masked-DAG
16.66 0.38
53.93 0.28
7.99 + 0.29
52.26 0.35
VI-DP-DAG
26.33 + 0.56
70.84 + 0.45
14.17 + 0.76
59.84 + 1.46
(e) SynTReN
Table 1: DAG structure learning results on synthetic and real datasets for all differentiable DAG learning models with AUC-PR and AUC-ROC scores (Higher is better). Un- and Dir- indicate scores for undirected and directed edges. Best scores among all models are in bold. Second best scores among all models are underlined.
keeping the edges such that P (*(((())))) relationships which are more likely to be present than absent according to the model.
.5. These edges intuitively correspond parent
We show the results for causal mechanisms learning in Tab. 2 Overall. DP-DAG is the most com- petitive model and achieves 9/11 best scores. Similarly to DAG structure learning, GraN-DAG is competitive for small graphs with 10 nodes but VI-DP-DAG outperforms all baselines for most larger graphs with 50 and 100 nodes. Interestingly, DP-DAG brings particularly significant improvement on real datasets compared to GraN-DAG and Masked- suggests that the potentially noisy ground-truth -ruth DAGs estimated by experts on these real datasets have an equivalent predictive power as the DAG learned by VI-DP-DAG. This aligns well with the intuition that VI-DP-DAG learn Granger causal relationships. Finally, evaluate in App. F6 the impact of the threshold choice f on the edge probabilities IP (U(U((()))) > t. We observe that the MSE score of DA-DAG achieves stable high performance regardless of the threshold value.
with scores very close to GT-DAG. This
8

---

Published as a conference paper at ICLR 2022
Training time. We evaluate the training time of all models single GPU (NVIDIA GTX 1080 Ti, 11 GB memory). Training time is particularly relevant for DAG structure learning since predicting the adjacency matrix A from new dataset represents a full training. Thus, real-world applications of DAG learning generally aim at fast training time.
We show the results in Tab. 3 The training of VI-DP-DAG is order of magnitude faster than all models on all datasets. Hence, assuming that training time is typically linearly correlated with compute cost, energy consumption and CO2 emission, the fast training DP-DAG significantly improves the applicability of DAG learning methods. In particular, VI-DP-DA is from x5 to x18 faster to train than CraN-DAG which is the second-best performing model for DAG structure learning and causal mechanisms learning. The training speed difference can be explained by the different optimization schemes. Indeed, Lagrangian optimization typically requires solving T 10 successive optimization problems (Zheng et al. 2018) while VI-DP-DAG only requires solving single optimization problem. Finally, by aggregating training and sampling time, VI-DP-DAG requires around 191 seconds to sample a DAG with 100 nodes from the learned approximate posterior distribution. In contrast, other sampling methods based on MCMC sampling require running the MCMC methods for 12 hours to
sample DAG with 100 nodes (Viinikka et al. 2020).
GraN-DAG
Masked-DAG
VI-DP-DAG
GT-DAG²
ER-10-10
0.61 0.01
0.93 + 0.02
0.58 + 0.01
ER-10-40
0.41 + 0.01
0.02
0.49
0.3
ER-50-50
0.82 + 0.01
0.97 + 0.0
0.8+
0.57 + 0.01
ER-50-200
0.84 0.01
0.97 0.0
0.0
0.48 + 0.01
ER-100-100
0.96 : 0.02
0.95 0.0
0.8
0.54 0.0
ER-100-400
0.98 0.0
0.9
0.48
SF-10-10
0.04
0.95 0.02
0.74
0.66 0.01
SF-50-50
0.01
0.99 0.0
0.0
0.79 0.01
SF-50-200
0.9 + 0.01
0.95 + 0.0
0.9
0.77 0.0
Sachs
1.16 - 0.05
0.93 + 0.05
0.8610.00
0.84 0.04
SynTReN
0.82 - 0.02
0.8 1 0.02
0.21 1.0
0.21 + 0.0
Table 2: Causal mechanisms learning results on all datasets with MSE score (Lower is better) on a test set i.e. ||X X12 where = fio X). Best scores among all models which jointly learn the adjacency matrix A and the causal mechanisms la are in bold. GT-DAG* is excluded since it is the ideal scenario when the ground-truth A is known at training and testing time.
DAG-GNN
GraN-DAG
Masked-DAG
DAG-NF
VI-DP-DAG
ER-10-10
2997 + 20
596
1997 = 30
5191 + 53
160 +
10-40
10727 = 145
613 + 12
1919 = 26
4962 + 44
86 + 3
ER-50-200
3485 + 110
1290 + 19
4279 = 73
5329 + 63
190 + 4
ER-50-50
3260 1: 72
1078 1: 22
5121 = 83
5531 1 71
194 13
ER-100-100
4077 + 50
2503 +
10530 + 212
4969 - 38
138 1
ER-100-400
5198 1 66
2391 101:60 59
10629 1 200
5008 1 36
19117
SF-10-10
1642 + 17
641
1873 29
4887 31
83 +-+
SF-50-200
2969 32
1138 -
4611 = 58
4901 23
112
SF-50-50
2910 + 20
1087 40
1640 60
4888 23
87
Sachs
1570
358 4: 13
1657 36
4970 26
67 1
SynTReN
8257 160
461 +
5120
4926 +
Table 3: Training time for all differentiable DAG learning models in seconds (Lower is better). Fastest training time among all models are in bold.
6 CONCLUSION
We propose a Differentiable Probabilistic model over DAGS (DP-DAG) which allows fast and differentiable DAG sampling and can be implemented in few lines of code. To this end, DP-DAG uses differentiable permutation and edges sampling based on Gumbel-Sinkhorn, Gumbel-Top-E and Gumbel-Softmax tricks. We propose VI-DP-DAG, DAG, new method combining variational inference and DP-DAG for DAG learning from observational data with continuous optimization. VI-DP-DAG guarantees valid DAG prediction at any time during training. In our extensive experiments, VI-DP- DAG performs favorably to other differentiable DAG learning baselines for DAG structure and causal mechanisms learning on synthetic and real datasets while training one order of magnitude faster.

---

Published as a conference paper at ICLR 2022
7 ETHICS STATEMENT
The Assessment List for Trustworthy AI (ALTAI) (oo.. 2020) includes reliability, transparency and Environmental well-being. Accurate and fast causal discovery from observational data is important to give meaningful and interpretable predictions at low energy cost. Therefore, VI-DP-DAG brings significant improvement regarding these values by performing high-quality DAG structure and causal mechanisms predictions at a low training cost.
While DP-DAG achieves high perforreree for DAG structure learning and causal mechanisms learning, there is always non-negligible risk that DP-DAG does not fully capture the real-world complexity. Thus, we raise awareness about the risk of excessive trust in causal predictions from Machine learning models. This is crucial when causal predictions are applied in domains subject to privacy or faimess issues (e.g. finance, medicine, policy decision making, etc). In particular, VI-DP-DAG does not provide any guarantee the causal interpretation of the edges in the final predicted DAG. Therefore, we encourage practitioners to proactively confront the model predictions for DAG structure and causal mechanisms to desired behaviors in real-world use cases.
REPRODUCIBILITY STATEMENT
We provide all datasets and the model code at the project page In App. Din in the appendix, we give detailed description for each dataset used in this paper. This description includes the task description, the dataset size, the number of nodes and edges and the vainn/vllidationttss splits used in the experiments. We further explain the hardware used for the experiments. In App. iin the appendix, we give a detailed description of the architecture and grid search performed for each model used in this paper. We describe the metrics used in the experiments in App.
REFERENCES
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation, 2013.
Remco R. Bouckaert. Probabilistic network construction using the minimum description length principle. In Symbolic and Quantitative Approaches to Reasoning and Uncertainty, 1993.
P. Brouillard, S. Lachapelle, A. Lacoste, S. Lacoste-Julien, and A. Drouin. Differentiable causal discovery from interventional data. In Advances in Neural Information Processing Systems, 2020.
Peter Bühlmann, Jonas Peters, and Jan Ernest, Cam: Causal additive models, high-dimensional order search and penalized regression. Annals of Statistics, 2014.
Eunice Yuh-Jie Chen, Yujia Shen, Arthur Choi, and Adnan Darwiche. Learning bayesian networks with ancestral constraints. NeurlPS, 2016.
David Chickering, Christopher Meek, and David Heckerman. Large-sample learning of bayesian networks is np-hard. JMLR, 2012.
David Maxwell Chickering. Optimal structure identification with greedy search. JMLR, 2002.
David Maxwell Chickering and David Heckerman. Efficient approximations for the marginal likelihood of bayesian networks with hidden variables. In Machine Learning, 1997.
Eu. Com. The assessment list for trustworthy artificial intelligence (altai) for self assessment, 2020.
Will Grathwohl, Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris Maddison. Oops took a gradient: Scalable sampling for discrete distributions. Proceedings of the 38th International Conference Machine Learning, 2021.
Julia Grosse, Cheng Zhang, and Philipp Hennig. Probabilistic dag search. In UAI, 2021.
https: https://www.damt wtt.mmm.......d....mmmmm fferenttff sampl lippiing
10

---

Published as a conference paper at ICLR 2022
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparametrizzation with gumbel-softmax. In ICLR, 2017.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In NeurIPS, 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. 2009.
Wouter Kool, Herke van Hoof, and Max Welling. Stochastic beams and where find them: The gumbel-top-k trick for sampling sequences without replacement. In ICML, 2019.
Jack Kuipers and Giusi Moffa. Partition meme for inference acyclic digraphs. Journal of the American Statistical Association, 2017.
Jack Kuipers, Polina Suter, and Giusi Moffa. Efficient sampling and structure learning of bayesian networks, 2020.
Sébastien Lachapelle, Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien. Gradient-based neural dag learning. In ICLR, 2020.
Gonzalo Mena, David Belanger. Scott Linderman, and Jasper Snock. Learning latent permutations with guubel--snkhon networks. In ICLR, 2018.
James Munkres. Algorithms for the assignment and transportation problems, 1957.
Ignavier Ng. Zhuangyan Fang. Shengyu Zhu, and Zhitang Chen. Masked gradient- based causal structure learning. CoRR, 2019.
Siqi Nic, Denis Maua, Cassio de Campos, and Qiang Ji. Advances in learning bayesian networks of bounded treewidth. In NeurlPS, 2014.
Teppo Ninimakii. Pekka Parviainen, and Mikko Koivisto. Partial order meme for structure discovery in bayesian networks. In UAI, 2011.
Teppo Niinimäki, Pekka Parviainen, and Mikko Koivisto. Structure discovery in bayesian networks by sampling partial orders. JMLR, 2016.
Young Woong Park and Diego Klabjan. Bayesian network learning via topological order. JMLR, 2017.
Max Paulus, Dami Choi, Daniel Tarlow, Andreas Krause, and Chris Maddison. Gradient estimation with stochastic softmax tricks. In NeurlPS, 2020.
Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. 1988.
Judea Pearl. Causality. 2009.
Jonas Peters, Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. JMLR, 2014.
Sebastian Prillo and Julian Eisenschlos. SoftSort: A continuous relaxation for the argsort operator. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Joseph Ramsey, Madelyn Glymour, Ruben sanchez. romero, and Clark Glymour. A million variables and more: the fast greedy equivalence search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images. International Journal of Data Science and Analytics, 2017.
R.W. Robinson. New Directions in the Theory of Graphs. 1973.
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, 2005.

---

Published as a conference paper at ICLR 2022
Mauro Scanagatta, Cassio P de Campos, Giorgio Corani, and Marco Zaffalon. Learning bayesian networks with thousands of variables. In NeurIPS, 2015.
Mauro Scanagatta, Giorgio Corani, Cassio P de Campos, and Marco Zaffalon. Learning treewidth- bounded bayesian networks with thousands of variables. In NeurIPS, 2016.
Spirtes, Glymour, and R. Scheines. Causation, Prediction, and Search. 2000.
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search, 2nd Edition. 2001.
Topi Talvitie, Aleksis Vuoksemmaa, and Mikko Koivisto. Exact sampling of directed acyclic graphs from modular distributions. In UAI, 2020.
Marc Teyssier and Daphne Koller. Ordering-basse search: A simple and effective algorithm for learning bayesian networks. In UAI, 2005.
DT. Tieleman and G. Hinton. Rmsprop: Divide the gradient by a running average of its recent magnitude, 2012.
Tim Van den Bulcke, Koenraad Leemput, Bart Naudts, Piet Remortel, Hongwu Ma, Alain Verschoren,
Bart De Moor, and Kathleen Marchal. Syntren: generator of synthetic gene expression data for design and analysis of structure learning algorithms. BMC bioinformatics, 2006.
Jussi Viinikka, Antti Hyttinen, Johan Pensar, and Mikko Koivisto. Towards scalable bayesian learning of causal dags. In NeurlPS, 2020.
Matthew J. Vowels, Necati Cihan Camgoz, and Richard Bowden. D'ya like dags? survey structure learning and causal discovery, 2021.
Antoine Wehenkel and Gilles Louppe. Graphical normalizing flows. In AISTAT, 2021.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gnn: Dag structure learning with graph neural networks. In ICML, 2019.
Yue Yu, Tian Gao, Naiyu Yin, and Qiang Ji. Dags with no curl: An efficient dag structure learning approach. In ICMI, 2021.
Bin Zhang, Chris Gaiteri, Liviu Gabriel Bodea, Zhi Wang, Joshua McElwee, Alexei A. Podtelezhnikov, Chunsheng Zhang, Tao Xie, Linh Tran, Radu Dobrin, Eugene Fluder, Bruce Clurman, Stacey Melguist, Manikandan Narayanan, Christine Suver, Hardik Shah, Milind Mahajan, Tammy Gillis, Jayalakshmi Mysore, Marcy F. MacDonald, John R. Lamb, David A. Bennett, Cliona Molony, David Stone, Vilmundur Gudnason, Amanda J. Myers, Eric E. Schadt, Harald Neumann, Jun Zhu, and Valur Emilsson. Integrated systems approach identifies genetic nodes and networks in late-onset alzheimer's discase. Cell, 2013.
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric Xing. Dags with no tears: Continuous optimization for structure learning. In NeurlPS, 2018.
12

---

Published as a conference paper at ICLR 2022
A AUGMENTED LAGRANGIAN OPTIMIZATION
In this section we recall the augmented Lagrangian optimization used by (Lachapelle et al. 2020
Ng al. 2019 Wehenkel & Louppe, 2021 Yu al. 2019 Zheng al. 2018). To this end,
denote the learned adjacency matrix A and the other model parameters by Hence, we can rewrite the augmented Lagrangian optimization problem follows:
min score X, (X,,,
(6)
S.L. ((A) =0
(7)
where ((A) = Tr(e*)- - n or I(A) Tr(I a A)" with a E R The function
smooth function over weighted adjacency matrices A R=*" which is equal zero when the corresponding graph G satisfies the DAG constraints. The augmented Lagrangian of the problem is defined as:
(c(A,,,) = (X, A) XA(A) 2
(((A))
where is the Lagrangian multiplier and e the penalty parameter. During training, practical optimization scheme is to update the parameters À and with the iteration:
Ak. 0p arg min L LA,
A.
AR+1 = Aa + (c)((A))
nCCK, if [T(AA))) 7(((A+-1)
Ck+1 [kk, otherwise
where >> 1 and >> 1 are hyper-parameters. The augmented Lagrangian optimization procedure is expensive since each Lagrangian iteration requires to solve minimization problem which can be done with stochastic optimization methods. In practice, previous works set that
10 and 7 and use stopping criterion h( (AA)) < [1e-6 le 8 le 103 to decide for the end of optimization where e constraint tolerance (Lachapelle et al., 2020 Ng et al.) 2019) 9 Yu et al. 2019 Zheng al., 2018). This generally leads to up to 10 Lagrangian iterations (Zheng al. 20188 and does not guarantee acyclicity of the final adjacency matrix (Lachapelle et 2020 Ng et al. 2019 Zheng al. 2018). Hence, the augmented Lagrangian requires final non-differentiable thresholding step to remove remaining cycles. In contrast, DP-DAG can always output valid sampled DAG solutions.
B GUMBEL-SOFTMAX, GUMBEL-SINKHORN GUMBEL-TOP-K
DISTRIBUTIONS
B. GUMBEL-SOFTMAX DISTRIBUTION (JANG ET AL.. 2017)
assume that a variable U on the (A: - -iddeennsio simplex follows a Gumbel-Softmax distribution with class probabilities Φ1 ..., Φx and temperature parameter i.e.:
U Gumbel-Softmax, (Ø)
The Gunbel-Softmax distribution becomes identical to the categorical distribution when the tempera- ture 7 approaches 0. The density of the Guftael-Softmax can be expressed as follows:
I U
P(U r) 7(
Σ 0
where ((k) denotes the Gamma function. We obtain sample U from the Gumbel-Softmax distribution by computing:
U, (log(d))+G./t
(loog())+&,))+-
whre G, are i.i.d. samples from Gu distribution. For differentiable sampling, the straight-through estimator (Bengio et al. 2013). Hence, the discrete variable one hot arg max max(U)) used for the forward pass, and the continuous variable U is used for the backward pass.
13

---

Published as a conference paper at ICLR 2022
B.2 TUMBEL-SINKHOL DISTRIBUTION (MENA ET AL.. 2018)
We assume that a variable II on the space of permutation matrix follows the Gumbel-Sinkhorn distribution with parameters |R"x and temperature parameter i.e.:
II Gumbel-Sinen Siabbell-inkhom,f (1+)
The Gumbel-Sinkhom distribution becomes identical to the Gumbel-Matching distribution when temperature approaches O. Neither the Gumbel-Matching the Gumbel-Sinkhorn distributions have tractable densities. We can obtain a sample II from the Gumbel--inkhon distribution by computing:
S( + G)
where S is the Sinkhorn operator which iteratively normalizes rows and columns of matrix and G E R is matrix of standard i.i.d. Gumbel noise. For differentiable sampling, we can use the straight-through estimator (Bengio et al., 2013). Hence, the discrete variable II Hungarian (TT) after applying the Hungarian algorithm (Munkres) 1957) to get a discrete permutation used for the forward pass, and the continuous variable II used for the backward pass. Finally, we can deterministically compute permutation by removing all Gumbel noise the forward pass.
B.3 GUMBEL-TOP- DISTRIBUTION (KooL ET AL. 2019
We assume that the variable the space of ordered sample of size & without replacement follows the Gumbel-Top-k distribution with parameters vA E R" i.e.:
Gumbel-Top-ke (v))
where is an optional temperature parameter usually set to 1. The density of the Gumbel-Top-K can be expressed as follows:
P(T = II
ZIEN, eti
where Nj = (m. -,.,.,,,,,,, This corresponds to subsequently sampling times without replacement from the categorical distribution over the nodes parametrized with with renormalization after each step. We can compute a sample ग from the Gumbel- Top-k distribution by computing:
arg top-k(e) + G)
where arg top-k is the operator selecting the indices with the top-k largest values and G E RR" is vector of i.i.d. Gumbel noise. Importantly, remark that the Gumbel-Topar distribution (i.e. k n) states the sorted perturbed log- bog-probabilities = Sort(ei (e) + G) where G E R" ~ Gumbel(O) defines a distribution over component- wise permutation (or linear ordering without replacement). Finally, we can deterministically compute permutation by removing all Gumbel noise in the forward pass.
C SOFTSORT OPERATOR (PRILLO & EISENSCHLOOS 2020
The SoftSort operator with temperature parameter is defined as:
SoftSon! = Softmax d(soot((s)1 11s)
where d is any differentiable almost everywhere, semi-metric function (e.g. d d= |= (). It defines family simple continuous relaxation for the permutation matrix corresponding to the argsort operator II aargwn((s) Indeed, we have:
lim SoftSort 7++
II sor(())
In particular, this limits holds almost surely if the entries of drawn from distribution that is absolutely continuous w.r.t. the Lebesgue measure on R. Further, note that SoftSort, is unimodal stochastic matrix and the permutation arg max max(SoftSort(()) is equal to arg sort(s).
14

---

Published as a conference paper at ICLR 2022
D DATASETS
All the datasets are split in train/validation/fest splits with 80% 10%% We use 10 different seeds for the dataset splits. We make all datasets available at the project page
Synthetic: We follow the data generation used in related works (Lachapelle et al. 2020; Ng et al. 2019. Peters et al. 2014). The graph structures A" are generated with the Erdös-Rény: Rényi (ER) or Scale- Free (SF), and the causal mechanisms Jü are generated from a (non-linear) Gaussian Process with RBF kernel of bandwidth one and with independent zero-mean Gaussian noises 6;- We considered different sizes of graphs including number of nodes n in {10, 50, 100) and number of edges in {10, 40, 50, 100, 200, 4003. In our experiments, we use 10 sampled datasets per setting. Each dataset contains 1000 samples.
Sachs (Sachs et al., 2005): The Sachs dataset has been widely used the DAG learning literature
(Koller & Friedman 2009; Lachapelle al. 2020 Ng et al., [019 Yu al., 2021 Zheng et al.
2018). It contains 853 observational data points. Each data point measures the expression level of
different proteins and phospholipids in human cells. The ground-truth DAG has 11 nodes and 17
edges.
SynTReN (Van den Bulcke et al., 2006): The SynTReN dataset has already been used in (Lachapelle
et al. 2020). Ten datasets are generated using the Syntren generator with software default parameters 1. Each dataset contains
except for th complex 2-regulator interactions probability which
500 samples. The ground-truth DAG has always 20 nodes.
E MODELS
In this section, provide more details about the training of all the models. We train all models single GPU (NVIDIA GTX 1080 Ti, 11 GB memory). All numbers are averaged over 10 seeds for the model initialization. We make available the implementation of VI-DP-DAG at the project page D
VI-DP-DAG (ours): VI-DP-DAC parametrizes the permutation probability (II) with Gumbel- Sinkhorn Gumbel-Top-Ke tricks, the edge probability P& (U)) with Gumbel-Softmax distribution and the causal mechanisms fe, with neural networks with 3 linear layers. We performed a grid search over the learning rate (r E [le 1e 2]. 1e__]] the number of hidden units per linear layer h E {8, 16, 64), or Gumbel-Top Top-K), the fixed prior The temperature
the permutation probability parametrization (i.c. probability P Prirr (Ui,) E [1e-2,1e 1e_ and the regularization factor À E 0., le 1. parameter for Gumbel-Sofftas distribution was fixed to r = 1 in all experiments. VI-DP-DAG is trained using the Adam optimizer (Kingma & Ba 2015). We perform early stopping by checking loss improvement on the validation every two epochs and patience p 10.
DAG-GNN Yu et al. 2019): DAG-GNN model proposes a Graph Neural Network (GNN) autoen- coder using variational inference. The latent variable is not the DAG adjacency matrix A but a noise
matrix Z. DAG-GNN uses the augmented Lagrangian approach for optimization. We follow the
recommendation for augmented Lagrangian optimization in (Lachapelle et al. 2020 Ng et al. 2019
Yu et al. 2019 Zheng et al. 2018) and set 17 = 10 and 7 4- We used a neural network with Innear layers for the encoder and decoder architectures. Further, we performed a grid-search on the learning rate Ir E -1, le -2] and the number of hidden units per linear layer la E {8, 16, 64). DAG-GNN trained using the Adam optimizer (Kingma Ba, (015).. This model does not di- rectly apply for consequence prediction from learned causal mechanisms as it does not predict the consequence values from the values of the learned parents. We use the implementation provided in https://githuu: htt./hh..ooooe.e. fis wishhmooon on 1233 DDG GNN
DAG-NE WWhennel & Louppe 2021): DAG-NF proposes to combine Normalizing Flows with an augmented Lagrangian optimization learn DAG structures from observational data. We follow the recommendation for augmented Lagrangian optimization in (Lachapelle et al. [2200] Ng et al.
2019 Yu et al., 2019 Zheng al. 2018) and set 1) 10 and 7 7. Further, performed grid-search on the monotomic or affine normalizer architectures, the conditioner and normalizer
htm
15

---

Published as a conference paper at ICLR 2022
learning rate Ir [1e 1e- 2]. the number of hidden units per linear layer in the conditioner and normalizer architectures h E {50, 100, 150, 200] and different 11 regularization X E [0, 60). We used a neural network with 3 linear layers for the conditioner and normalizer architectures and the embedding size was set to set to 30 as suggested by the authors Wehenkel & Louppe (202T) DAG-NF is trained using the Adam optimizer (Kingma & Ba 2013). This model does not directly apply for consequence prediction from learned causal mechanisms as it does not predict the consequence values from the values of the learned parents. We use the official implementation provided in https: http://ggtttu.uu.. com/ hwtp://w......eeeeeeeee///aaaa.a watpee/wwweeeaappcaaaaoooooooooe
Gran-DAG (Lachapelle et al., 2020): Gran-DAG proposes to compute the adjacency matrix from the learned weight of the non-linear causal relationships. Gran-DAG uses the augmented Lagrangian approach for optimization. We follow the recommendation for augmented Lagrangian optimization in (Lachapelle et al. 2020 Ng et al. 2019 Yu et al. 2019 Zheng et al. 2018) and set 1j 10 and 7
We used a neural network with Tinear layers. Further, we pertormed a grid-search on the learning rate Ir E [Le- 1e 3 and the number of hidden units per linear layer f E {8, 16, 64). Gran-DAG is trained using the RmsProp optimizer (Tieleman & Hinton 2012). This model can be used for consequence prediction from learned causal mechanisms. Indeed, it uses architecture similar to DP- DAG which aims at predicting the values of consequence values from values of the learned parents. We use the official implementation provided in
com/ kurowa SaeesaannGrraaaaa
Masked-NN (Ng et al. 2019): Masked-NN proposes to learn the binary adjacency matrix A by combining the Gumbbel-Sottmax distribution with the augmented Lagrangian approach for opti- mization. We follow the recommendation for augmented Lagrangian optimization in (Lachapellc) al. 2020 Ng al. 2019; Yu et al., 2019. Zheng et al. 2018) and set v) 10 and 7 = 1. We used a neural network with 3 linar layers. Further, we performed a grid-search on the learning rate Ir e [1e-4, le ?] and the number of hidden units per linear layer E {8, 16, 64]. Masked-NN is trained using the Adam optimizer (Kingma & Ba 2015). This model can be used for consequence prediction from learned causal mechanisms. Indeed, it uses an architecture similar to DP-DAG which aims at predicting the values of consequence values from values of the learned parents.
GT-DAG: GT-DAG a new baseline with the exact same architecture as VI-DP-DAG except that it uses the ground-truth DAG A" instead of DAGs sampled from DP-DAG during learning. Hence, this baseline can be considered as the best-case scenario when learning the causal mechanisms fi from observational data. Further, we performed a grid grid-search on the learning rate Ir E [le- 1e and the number of hidden units per linear layer h E (8. 16, 64). GT-DAG is trained using the Adam optimizer (Kingma& Ba 2015). We perform early stopping by checking loss improvement on the validation set every two epochs and patience p 10.
CAM (Bhhlmann et al. 2014): CAM proposes to learns DAGs structure by (1) using Preliminary Neighbor Selection (PNS), (2) greedily searching for edges with the largest Likelihodd gain, and finally (3) pruning spurious edges with significance testing of covariates (Bühlmann et al. [0114). The preprocessing PNS step and the postprocessing steps not differentiable but are decisive for high performance. This motivates other approaches like Lachapelle et al. (2020): Ng et al. (2019) to use the same processing steps.
F ADDITIONAL RESULTS
F.1 DAG SAMPLING
In this section, we compare the DAG sampling performances of DP-DAG using Gumbel-Sinkhen or Gumbel- Tookk parametrization for permutation sampling. To this end, we sample 30 DAGs with 10 to 200 nodes and compute the mean and the variance of the sampling time. We show results for the sampling time in Fig. The Gumbel-Top- parametrization is significantly faster than the Gumbel- Sinkhorn parametrization. This is expected from the complexity analysis of the two permutation parametrization. of On²²).
has a complexity of O(n)) while Gumbel-Top-k has a complexity
Further, we evaluate the capacity of the two differentiable sampling methods for learning DAGs when the ground-trum truth DAG is observed. To this end, the direct MSE error between a new sampled DAG A and the ground-truth DAG A is used as the loss each iteration. This task aims at evaluating
16

---

Published as a conference paper at ICLR 2022
Sampling time (seconds)
0.4
Sampling time (seconds)
Gumbel-Sinkhorm
Gumbel-Top-k
0.0010
Gumbel-Top-k
0.2
0.0009
0.0008
0.0
50
100
150
200
50
100
150
200
Number of nodes
Number of nodes
Figure 4: DAG sampling time of DP-DAG using Gumbel- Gumbel-Sinkhom Gumbel-Top-k parametrization for permutation sampling. The Gumbel-Top-e parametrization significantly faster for sampling.
whether the DAG sampling optimization scheme is reliable optimization scheme on a simple toy task. This is priori not guaranteed since the DAG sampling space is very large. However, and Gumbel-Tope -To-- parametrizations recover almost
observe in Tab. that both Gumbel-Sinkhng perfectly the ground-truie truth DAG A for all graph sizes and graph types. These results are particularly significant since each dataset setting is averaged over 10 sampled graphs and 4 learning rates Ir E (10e-1, 10e -2 10e -3 10. These experiments validate that DP-DAG is reliable method for fast and differentiable DAG sampling.
Gunbel-Sinkhorn
Gumbel-Top-k
Gumbel-Sinkhorn
Gumbel-Top-k
ER-10-10
1. 0.0
1.0 0.0
ER-10-10
1. 0.0
1.0 =: 0.0
ERR-10400
0.97 + 0.02
0.98 + 0.0
ERR-10400
0.97 0.0
0.99 + 0.0
ER-20-80
0.95 + 0.04
0.98 + 0.03
ER-20-80
0.96 0.0
0.98 0.0
ER-50-50
0.94 + 0.0G
0.95 + 0.05
ER-50-50
0.96 0.0
0.97 0.0
ER-100-100
0.9 0.1
0.96
ER-100-100
0.93 0.001
0.97 0.0
ER-1100-200
0.92 + 0.06
0.97 + 0.03
ER- 100-000000
0.94 0.0
0.98 + 0.0
ER-100-400
0.91 + 0.06
0.95 1 0.05
ER-100-400
0.94 0.0
0.97 + 0.0
SF-10-10
SF-10-10
0.94
SF-10-40
0.95 +: 0.03
0.94 0.00
SF-10-40
0.96 0.0
0.99
SF-20-20
0.89 0.06
SF-20-20
0.92 0.0
0.95
SF-20-80
0.98 + 0.08
1.00
SF-20-80
0.98
1.0+00
SF-50-50
0.92 0.06
0.006
SF-50-50
0.0
0.97
SF-50-200
0.97 + 0.03
0.98 + 0.02
SF-50-200
0.98
0.99 + 0.0
SF-100-100
0.89 0.1
0.94
SF-100-100
0.92
0.96 +.0 0.0
SF-100-400
+ 0.04
0.02
SV-100-400
Table 4: AUC-PR
Table 5: AUC-ROC
Table 6: Direct DAG structure learning results on synthetic datasets using differentiable sampling optimization with AUC-PR and AUC-ROC scores (Higher is better). At each iteration, the direct MSE error between a new sampled DAG A and the ground-truth DAG A* is used as loss. Each results is averaged 10 sampled graphs and 4 learning rates. Both Gumbel-Sinkhon sampling methods lead to high performance for all graph sizes and graph types.
and Gumbel-Top-k
F.2 DAG STRUCTURE LEARNING WITHOUT NON-DIFFRRENTIBLEE PROCESSING
We show the additional results for differentiable DAG structure learning on synthetic and real datasets in Tab. 7 While GraN-DAG competes with VI-DP-DAG small synthetic datasets with around 10 nodes, DP-DAG outperforms all baselines on all larger synthetic datasets with 50 100 nodes for both ER and SF graph types. On real datasets, no baseline consistently outperforms VI-DP-DAG which obtains 4/8 best scores and second-best scores on the remaining evaluations.
Furthermore, we show results for DAG structure learning for VI-DP-DAG, GraN-DAG and Masked- DAG using the mean and the standard deviation of the SHD scores between the ground-trum -trth dag adjacency matrix A and the thresholded predicted adjacency matrix P (U*()=))) for different threshold choices Fig. (5) Thresholds are ordered from sparser graphs (i.e. larger thresholds) to denser graphs (i.e. smaller thresholds). We observe that models might be sensitive
or AG >
17

---

Published as a conference paper at ICLR 2022
14
+T 0 DSS
Grll 366
12
DUE
(a) ER-10-10
(b) ER-10-40
(c) ER-50-50
Mecondiatt:
150
Nesiniratt
50-
134
1.0
20
(d) ER-50-200
(c) ER-100-1110
ER-100-400
19-2-24G
202
350
140
15
5 22
54
21
100
16
gg) SF-10-10
(h) SF-50-50
(i) SF-50200
Figure 5: DAG structure learning results for different graph types and sizes for all differentiable VI-DP-DAG, GraN-DAG and Masked-DAG with SHD scores with different thresholds from sparser denser graphs (Lower is better).
the threshold choice thus motivating the of threshold agnostic metrics such that AUC-PR and AUC-ROC. However, we observe that VI-DP-DAG generally achieves the best performances for different graphs types and graph sizes given the best possible threshold selection.
F.3 DAG STRUCTURE LEARNING WITH XON-DIFFERENTIABLE PROCESSING
We show the additional results for DAG structure learning with non-differentiable pre- and post- processing in Tab. [ and Tab. 9 In these experiments, we apply the default pre- pre-processing PNS and post-processing CAM pruning steps to CAM, GraN-DAG, Masked-DAG suggested by the original papers. We similarly apply CAM pruning to the final results of VI-DP-DAG. While the greedy CAM the best performing model for most synthetic datasets, VI-DP-DA maintains competitive performance on all datasets and is the best performing model on real datasets (i.c. 7/8 best scores). The pre- and post-proces
steps are decisive for the augmented Lagrangian optimization baselines GraN-DAG and Masked-DAG to achieve performance competitive with VI-DP-DAG, e al. (2020) makes similar observations on the dependence on PNS and CAM pruning steps. We show the comparison of GraN-DAG and VI-DP-DAC with and without additional processing steps in Tab. 10 and Tab. [] GraN-DAG is indeed more dependent on additional processing steps than VI-DP-DAG to achieve high performance.
F.4 NON-DIFFERENTIABBEE PROCESSING TIME
We show additional results of the processing time (inel. the mean and standard error of the mean over 5 runs) for the non-differentiable PNS pre-proe preprceeesing the CAM algorithm and the DAG pruning processcns (Bühlmann et al. 2014) for ER- 10-40, ER-50-200, ER-100-400 with with different number of nodes in Tab. [2] Each of this processing step becomes significantly slower tha VI-DP. DAG for larger number of nodes. In particular ER-100-400, the PNS pre- pre-processing is around x4
18

---

Published as a conference paper at ICLR 2022
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
DAG-GNN
44.20 1.66
63.55 + 1.06
18.35 0.9
51.59 + 1.0
DAG-NF
28.22 + 0.88
54.07 + 0.63
19.47 0.88
55.41 +.61
GraN-DAG
91.17 + 0.69
96.76 0.29
89.96 0.69
97.38 0.25
Masked-DAG
44.74 + 1.77
66.58 + 1.03
30.23 1.8 1.8
62.28 1.03
VI-DP-DAG
82.88 + 1.48
95.00 + 0.51
62.61 2.84
83.27 + 1.36
(a) ER-10-10
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
DAG-GNN
85.31 = 0.53
55.86 = 0.69
49.26 + 0.79
55.76 + 0.67
DAG-NF
83.46 0.29
56.72 0.43
51.93 0.43
GraN-DAG
9
89.20 0.38
93.54 0.39
95.26 + 0.34
Masked-DAG
84.05 0.3
58.94 0.31
48.92 + 0.42
57.19 + 0.35
VI-DP-DAG
94.59 = 0.5
86.09 = 1.07
79.42 + 0.97
83.93 + 0.76
(b) ER-10-40
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
DAG-GNN
16.20 + 1.03
52.20 0.78
5,52
51.80
DAG-NF
0.13
50.32 = 0.08
2.35
30.22 0.05
GraN-DAG
42.97 1.1
71.40 0.7
38.07 0.97
7.65
Masked-DAG
11.29
53.97 0.24
7.66
53.26
VI-DP-DAG
7.870
97.26 0.12
52.95 0.95
80.85 = 0.46
(c) ER- 50-50
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
DAG-GNN
7.46
49.14 0.39
2.16
50.43 0.59
DAG-NE
2.12
50.13 0.09
1.10
50.12 + 0.06
GraN-DAG
19.67 = 0.58
64.47
1.46
60.49 + 0.38
Masked-DAG
8.78 - 0.31
53.46
53.29 0.16
VI-DP-DAG
48.38 + 0.88
94.46 0.16
29.34 0.93
72.93 + 0.55
(d) ER-100-100
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
DAG-GNN
38.91 1.56
46.56 1.56
20.04 0.62
49.83 + 0.63
DAG-NF
24.03 : 0.87
5
11.78 0.46
50.93 + 0.39
GraN-DAG
1414::.0 93.14
97.59 0.28
98.85 + 0.14 0.14 9.701
Masked-DAG
48.96 + 1.79
69.21 + 1.05
39.42 2.22
66.92 + 1.2
VI-DP-DAG
77.26 + 0.97
93.47 + 0.4
66.35 1.69
87.05 + 1.18
(e) SF-10-10
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
DAG-GNN
7.76 0.26
49.24 = 0.58
3.36 + 0.14
49.66 + 0.52
DAG-NF
3.92 + 0.0
49.83 0.0
1.96 0.0
49.92 +.0 0.0
GraN-DAG
21.82 + 0.64
64.16 0.51
18.1
62.78 - 0.47
Masked-DAG
10.39 0.23
53.37 0.12
6.11 + 0.22
52.33 0.1
VI-DP-DAG
46.67 + 0.8
80.50 + 0.49
23.25 + 0.89
60.74 0.7
(1 SF-50-50
Table 7: DAG structure learning results synthetic and real datasets for all differentiable DAG learning models with AUC-PR and AUC-ROC scores (Higher is better). Un- and Dir- indicate scores for undirected and directed edges. Best scores among all models are in bold. Second best scores among all models are underlined.
19

---

Published as a conference paper at ICLR 2022
1.0
0.5
Restive goar store
6.0
0.90
0.95
6.
-1.0
GraN-DAG
Vi DAG
0.85
GroN-DAG
VI DAG
-1.0
-0.5
V--P-DAG
Grak DAG
-1.
Masked
0.75
Masted DAG
1.5
perturbasiors
(a) ER-10-10
(b) ER-100-400
(c) SynTReN
VI-I--DGG
Grai4-Do DAG
Retalive graph Scoro
Reailie graph Store
DAG-M NF
V-OP-DA
-30
GraNiDeG
GraN--AAG
Maskeri- DAG
Wosked DAG
DAG CNN
DAG-CIN
DAG-IF
DAG NF
Number tutbatioon
Number perturbations
Number berturbetiors
(d) 10-10-10
(c) 1R0-100-00
(f) SynTReN
Figure 6: Relative confidence scores of perturbed graphs Á obtained by randomly moving edges from the ground-truth DAG adjacency matrix A Fig. 66 show the results for models with architecture similar to VI-DP-DAG: Fig. 6d 6f show the results for models
slower than VI-DP-DAG, the CAM algorithm is at least more than x900 slower than VI-DP-DAG since did not finish in less than days, and the DAG pruning post-processing is around x23 slower than VI-DP-DAG.
F.5 DAG STRUCTURE LEARNING UNDER PERTURBATIONS.
We evaluate if the models confidently assign lower confidence scores to perturbed versions of the ground-truth adjacency matrix A To this end, we create a perturbed matrix A by randomly moving different number of edges from A and compute its relative confidence score. The relative confidence score assigned by model is the sum of the edges scores of the perturbed matrix À normalized by Di S. 1 As where S.j (((U(())))) for VI-DP-DAG and the score of the clean matrix A' i.c. E., S, A5,
Siy = Au for other models using Lagrangian optimization.
We report the mean and standard deviation of the relative confidence score over 10 sampled perturbed graphs in Fig. []] As desired, VI-DP- confidently assigns a higher score to the ground-truit matrix and lower scores to graphs with larger perturbations. This indicates that the DAG sampling optimization of DP-DAG converges to reliable probabilistic model over DAGs. In contrast, GraN- DAG and Masked-DAe -DAG assign significantly more noisy scores to perturbed graphs (see e.g. Fig. (bb). Further, other baselines do not confidently assign strictly decreasing scores to graphs with larger perturbations.
F.6 CAUSAL MECHANISMS LEARNING
We show causal mechanisms learning results when varying the threshold used compute the adjacency matrix A from the edge probabilities A.j = 1 (U,)Ui))))> of VI-DP-DAG in Fig. 7 The MSE scores of VI-DP-DAG are almost insensitive the threshold value except for probability thresholds close to 1. Intuitively, DP-DAG predicts a too sparse DAG adjacency matrix for threshold close to thus removing important Granger-causes to predict the node values z;.
20

---

Published as a conference paper at ICLR 2022
34
NaROCOAG
(a) ER-10-10
(b) ER-10-40
ER-50-50
03
10
18
09
(d) 25-250000
(c) ER-100-100
(f) ER-100-400
0110
641
26.566
Grth ONU
10
(g) SF-10-10
(h) SF-50-50
(i) SF-50-200
ERC
Twak
975
(i) Sachs
(k) SynTRen
Figure 7: Causal mechanisms results on datasets with MSE score (Lower is better) on a test set i.c. || X|2 where X, = fi.e (A, o X). We vary the threshold t to compute the adjacency matrix A from the edge probabilities Aij (U,;W;;)))> of VI-DP-DAG. For indication, the MSE of GraN-DAG, Masked-DAG and GT-DAG are plotted with straight lines.
21

---

Published as a conference paper at ICLR 2022
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
CAM
92.60 + 0.17
98.89
92.56 = 0.17 0.17
98.96 = 0.0
GraN-DAG
87.45 0.76
93.
86.63 + 0.81
93.25 0.41
Masked-DAG*
11.34 0.45
53.97 = 0.24
7.71 0.4
53.27 +
VI-DP-DAG*
90.28 0.46
95.93 + 0.24
61.13 + 0.87
85.21 0.38
(a) ER-50-50
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
CAM
49.35 0.05
74.45 0.04
41.35 + 0.06
73.60 0.04
GraN-DAG*
49.85 + 0.66
70.91 + 0.44
44.78 = 0.74
70.78 + 0.44
Masked-DAG*
17.55 0.14
51.09 0.05
9.14 0.09
50.81 + 0.04
VI-DP-DAG=
53.77 + 0.36
73.25 + 0.25
36.54 + 0.34
68.08 0.2
(b) ER-50-200
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
CAM*
56.00 + 0.0
79.46 + 0.0
49.97 + 0.0
78.24 + 0.0
GraN-DAG*
38.28 0.39
66.95 0.24
35.39 + 0.4
66.85 0.24
Masked-DAG*
9.03 + 0.12
50.72 + 0.06
4.76 +: 0.1
50.55 + 0.06
VI-DP-DAG*
72.71 0.23
22.32 + 0.93
64.57 = 0.39
(c) 100-100-400
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
CAM
53.66 0.16
79.43 0.0
52.86 = 0.16
79.51 0.0
GraN-DAG*
49.86 + 0.99
73.96 + 0.52
47.71 + 0.99
73.46 0.5
Masked-DAG*
10.39 0.23
53.37 0.12
6.11 + 0.22
52.33 0.1
VI-DP-DAG*
50.56 + 0.96
74.78 0.52
25.41 + 0.97
65.99 0.54
(d) SF-50-50
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
CAM
32.45 + 0.13
63.10 0.04
28.45 + 0.13
63.17 + 0.04
GraN-DAG*
29.28 0.41
60.11 + 0.24
24.74 + 0.44
60.12 0.24
Masked-DAG*
14.39 + 0.13
51.64 + 0.06
7.23 0.12
50.97 + 0.06
VI-DP-DAG*
30.17 0.29
60.85 0.17
15.78 =
0.29 0.29
57.04 + 0.17
(e) SF-50-200
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
CAM
32.62 0.04
55.07 + 0.06
18.69 + 0.03
56.98 + 0.02
GraN-DAG*
$0.79-0.1
52.07 + 0.21
16.38 0.2
52.22 0.26
Masked-DAG#
36.98 0.25
55.13 0.15
17.74 0.31
51.71 = 0.23
VI-DP-DAG*
40.29 0.4
59.00 = 0.06
19.11 0.44
54.30 = 0.33
(f) Sachs
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
CAM
18.27 0.03
63.16 0.03
7.57 0.01
56.16 0.01
GraN-DAG*
16.30 + 0.34
54.91 0.21
9.55 +.24
53.77 + 0.19
Masked-DAG*
17.24 0.4
54.22 0.32
8.78
52.63 0.38
VI-DP-DAG=
15.11 0.91
76.23 + 0.68
17.84
64.32 + 1.05
(g) SynTReN
Table 8: DAG structure learning results on synthetic and real datasets for all differentiable DAG learning models with non-differentiable processing denoted with star * Performance are evaluated with the AUC-PR and AUC-ROC scores (Higher is better). Un- and Dir- indicate scores for undirected and directed edges. Best scores among all models are in bold. Second best scores among all models are underlined.
22

---

Published as a conference paper at ICLR 2022
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
CAM
100.00 + 0.0
100.00 + 0.0
100.00 + 0.0
100.00 + 0.0
GraN-DAG*
94.80 + 0.76
98.68 + 0.22
86.34 + 1.92
95.96 + 0.55
Masked-DAG*
45.56 + 1.64
66.35 + 1.02
29.69 + 1.78
61.96 1.0
VI-DP-DAG*
88.17 + 1.07
96.18 + 0.43
66.17 + 2.66
87.58 + 1.0
(a) ER-10-10
Models
Un-AUC-PR
Un-AUC-ROC
Dir-UUC-PR
Dir-AUC-ROC
CAM
89.56 0.0
78.09 = 0.0
79.56 0.0
8..54
GraN-DAG*
98.79 + 0.38
84.43 0.78
86.00 = 0.55
89.28 0.37
Masked-DAG*
84.00 = 0.31
58.82 = 0.32
48.77 = 0.43
57.06 + 0.36
VI-DP-DAG*
93.23 0.46
83.11 0.92
75.98 + 0.83
80.75 0.62
(b) 10-10
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
CAM
82.17 0.0
95.40 0.0
75.07 0.0
93.43 + 0.0
GraN-DAG*
77.87 + 0.47
90.08 + 0.28
76.61 + 0.53
89.71 + 0.29
Masked-DAG#
8.78 + 0.31
53.46 0.16
7.41 0.32
53.29 0.16
VI-DP-DAG*
79.39 0.57
93.78 + 0.21
46.11 + 1.13
80.34 + 0.37
(c) ER-10001000
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
CAM
100.00 0.0
100.00 0.0
100.00 + 0.0
100.00 + 0.0
GraN-DAG*
90.89 + 1.15
94.44 0.7
86.85 + 1.36
93.79 0.68
Masked-DAG*
48.07 + 1.63
68.25 1.0
38,96 + 1.99
66.48 +
VI-DP-DAG*
83.76 0.88
90.65 0.52
71.25 + 1.65
85.52 0.81
(d) SF-10-10
Table 9: DAG structure learning results on synthetic and real datasets for all differentiable DAG learning models with non-differentiable processing denoted with star * Performance evaluated with the AUC-PR and AUC-ROC scores (Higher is better). Un- and Dir- indicate scores for undirected and directed edges. Best scores among all models are in bold. Second best scores among all models are underlined.
23

---

Published as a conference paper at ICLR 2022
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
GraN-DAG
42.97
71.40 0.7
38.07 0.97
70.27 = 0.65
0.65
GraN-DAG*
87.45 0.76
93.51 +
86.63 + 0.81
93.25 + 0.41
VI-DP-DAG
75.70 + 0.8
97.26
0.12
52.95 + 0.95
80.85 + 0.46
VI-DP-DAG
90.28 0.46
95.93 0.24
6 0.87
85.21 = 0.38
(a) ER-50-50
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
GraN-DAG
25.11 = 0.4
56.57 0.35
17.61 0.47
56.35 = 0.34 70.78 = 0.44
GraN-DAG
49.85 = 0.66
70.91 + 0.44
44.78 0.74
VI-DP-DAG
62.08 = 0.34
84.53 0.25
11.70
71.08 = 0.33
VI-DP-DAG
53.77 + 0.36
73.25 0.25
36.54 + 0.34
68.08 + 0.2
ER-50-200
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
GraN-DAG
9.73 0.11
52.82 0.11
4.42 0.04
51.04 + 0.06
GraN-DAG*
38.28 + 0.39
66.95 + 0.24
35.39 0.4
66.85 + 0.24
VI-DP-DAG
36.98 = 0.98
77.23 0.63
1.07
60.35 1.01
VI-DP-DAG
44.45 = 0.61
72.71 + 0.23
22.32 0.93
64.57 0.39
(c) ER-100-400
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
GraN-DAG
21.82 = 0.64
64.16
18.12
62.78 73.46
GraN-DAG*
49.86 + 0.99
73.96 +
VI-DP-DAG
46.67 + 0.8
80.50 0.49
23.25
0.89
60.74 0.7
VI-DP-DAG*
50.56 + 0.96
74.78 + 0.52
25.41 + 0.97
65.99 = 0.54
(d) SF-50-50
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
GraN-DAG
18.75 + 0.29
54.76 + 0.17
12.35 + 0.32
53.31 + 0.43
GraN-DAG*
29.28 + 0.41
60.11 + 0.24
24.74 0.44
60.12 + 0.24
VI-DP-DAG
33.81 = 0.39
08.18
17.46 +
59.70 0.65
VI-DP-DAG
30.17 + 0.29
60.85 0.17
15.784..2
57.04 0.17
SFF50-200
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
GraN-DAG
34.28 + 0.32
54.57 + 0.36
19.95 + 0.35
55.91 = 0.33 52.22 + 0.26
GraN-DAG*
30.79 + 0.2
52.07 0.21
16.38 0.2
VI-DP-DAG
43.37 + 0.55
59.78 + 0.62
22.96 0.81
60.02 = 0.91
VI-DP-DAG*
40.29 + 0.4
59.00 0.06
19.11 0.44
54.30 = 0.33
(1) Sachs
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
GraN-DAG
19.89 + 0.4
62.29 0.31
15.39 + 0..4
63.91 + 0.34
GraN-DAG*
16.30 + 0.34
54.91 0.21
9.55 1.25
53.77 0.19
VI-DP-DAG
26.33 + 0.56
70.84 0.45
14.17 0.76
59.84 1.46
VI-DP-DAG*
35.11 = 0.91
76.23 0.68
17.84 0.98
64.32 = 1.05
(g) SynTReN
Table 10: DAG structure learning results synthetic and real datasets for VI-DP-DAG and the second best baseline GraN-DAG with and without non-differentiable processing. Models using additional processing denoted with star * Performance scores (Higher is better). Un- and Dir- indicate scores for undirected and directed edges. GraN-DAG more dependent additional processing steps than VI-DP-DAG to achieve high performance.
evaluated with the AUC-PR and AUC-ROC
24

---

Published as a conference paper at ICLR 2022
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
GraN-DAG
91.17
96.76 0.29
99.96
07.88 95.96 = 0.55
GraN-DAG#
94.80 0.76
98.68 0.22
8.93
VI-DP-DAG
82.88 = 1.48
95.00 + 0.51
62.61 2.84
83.27 = 1.36
VI-DP-DAG*
88.17 = 1.07
96.18 0.43
66.17 2.66
87.58 = 1.0
(a) ER-10-10
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
GraN-DAG
96.47 + 0.14
89.20 + 0.38
93.54 + 0.39
9 0.34 89.28 = 0.37
GraN-DAG*
93.79 + 0.38
84.43 0.78
86.00 0.55
VI-DP-DAG
94.59 0.5
86.09 + 1.07
79.42
83.93 = 0.76
VI-DP-DAG
93.23 + 0.46
83.11 0.92
75.98:0.88
80.75 = 0.62
(b) 10-40
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
GraN-DAG
19.67 + 0.58
64.47 + 0.5
11.63 0.46
60.49 : 0.38 89.71 = 0.29
GraN-DAG*
77.87 + 0.47
90.08 0.28
76.61 0.53
VI-DP-DAG
48.38 = 0.88
94.46 +.16
29.34
72.93 = 0.55
VI-DP-DAG
79.39 = 0.57
93.78 0.21
46.11
80.34 0.37
(c) ER-100-100
Models
Un-AUC-PR
Un-AUC-ROC
Dir-AUC-PR
Dir-AUC-ROC
GraN-DAG
93.14 0.75
97.59 0.28
93.01 0.77
98.85 0.14
GraN-DAG*
90.89 1.15
94.44 + 0.7
86.85 1.36
93.79 : 0.68
VI-DP-DAG
77.26 + 0.97
93.47 + 0.4
66.35 + 1.69
87.05 + 1.18
VI-DP-DAG=
83.76 + 0.89
90.65 + 0.52
71.25 + 1.65
85.52 + 0.81
(d) SF-10-10
Table 11: DAG structure learning results on synthetic and real datasets for VI-DP-DAG and the second best baseline GraN-DAG with and without non-differentiable processing. Models using additional processing are denoted with star Performance are evaluated with the AUC-PR and AUC-ROC scores (Higher is better). Un- and Dir- indicate scores for undirected and directed edges. GraN-DAG is more dependent on additional processing steps than VI-DP-DAG to achieve high performance.
PNS
CAM
Pruning
ER-10-40
11.91 0.09
14.42 0.42
ER-50-200
150.54 0.03
22292.7 591.13
667 03 = 15.59
ER-100-400
750.14 8.53
> 2 days
6114.66 62 + 495.93
Table 12: Processing time in seconds of the non-differentaible PNS pre- prepprocessing, the CAM algorthm and the DAG pruning (üühlmann et al. 2014).
25


Reviews:
[{"review_id": "oU6su8I5uPv", "reviewer": "Reviewer_cRyc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "_Strengths_\n* The method is simple and clever. Rather than relying on relaxations during the forward pass, the Gumbel Straight-Through estimator allows the relaxation to happen only during gradient estimation. Additionally, the errors in the straight-through estimators for edge and order parameters do not compound due to the probabilistic model.\n* The experimental evaluation is thorough. The model is evaluated on both synthetic (Erdos-Renyi, Scale-Free, and SynTReN) and real data (Sachs) of various sizes. The results are convincing, with the proposed method VI-DP-DAG either achieving the best performance or comparable for structure learning. A similar trend holds for causal mechanism learning, where VI-DP-DAG outperforms or ties baselines in all but the two smallest settings.\n* Timing results are very impressive. VI-DP-DAG obtains 5x-10x speedup over baselines. In conjunction with the accuracy results, this is a strong contribution.\n* The paper is clearly written.\n\n_Weaknesses_\n* I did not find any obvious weaknesses.\n\n_Questions_\n* How many epochs does each method take to converge? In other words, what is the total training time for each method?\n* What are the accuracies and speeds for non-differentiable methods?\n\n_Feedback_\n* Can you add a table with DP-DAG and second best method with and without pre/post processing to the appendix? This would make it easier to see the claim that DP-DAG is less dependent on pre/post processing compared to other methods.\n* Table 2 (bottom left): GraN-DAG is bolded when it should not be.\n* Given the citation of Vowels et. al., 2021 after the discussion of AUC vs Structural Hamming Distance evaluation metrics in the results section, I could not find discussion in Vowels et. al. on a comparison between AUC and SHD. How is this citation relevant in this setting, or did I miss something?\n", "summary_of_the_paper": "This paper presents a differentiable probabilistic model (DP-DAG) over DAGs that retains accuracy over comparable differentiable DAG models. In combination with variational inference for training, VI-DP-DAG demonstrates large gains in computational efficiency at the cost of an intractable exact scoring function (ie computing $P_{\\phi,\\psi}(A)$). The computational gains come from the factorization of the DAG distribution into the product of orderings and edges, which results in intractable scoring as all valid permutations must be marginalized over in order to score a graph. However, this is not an issue: the pathwise derivative is used during training, requiring only a differentiable sampling procedure, and evaluation does not require scoring.", "summary_of_the_review": "I recommend this paper for acceptance. It proposes a simple method that obtains accuracy competitive to baselines (often exceeding them) at much faster training speeds (between 5x and 10x).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fwXej6MiRT_", "reviewer": "Reviewer_PQoz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Strengths: \n- Contrary to previous work, the proposed method does not pre- or post-processing to make sure the returned graph is DAG.\n- It is easy to implement the algorithm in a few lines of code.\n- The current work presents a differentiable DAG sampling which I think is novel in this field.\n\nWeaknesses:\n- From the experimental results, it is hard to conclude that the current work is better than previous works in terms of both processing time and estimation error. It would be great if the authors can derive the computational complexities of other previous works and compare them with their method. From table 9, we can see that the performances of all methods get better as we use non-differentiable processing and even other methods (like CAM) might achieve higher performance. \n- It is unclear whether the DAG sampler is unbiased, i.e., it selects a DAG uniformly from the Markov equivalence class as number of samples goes to infinity.\n\n", "summary_of_the_paper": "The authors proposed an algorithm for sampling DAGs that is suited for continuous optimization. The sampling algorithm has two main steps: In the first step, a causal order over the variables is selected. In the second step, edges are sampled based on the selected order. Moreover, based on this algorithm, they proposed a method in order to learn the causal structure from the observational data. The causal structure learning algorithm is guaranteed to output a DAG at any time and it is not required any pre- or post-processing unlike previous work. ", "summary_of_the_review": "As far as I know, this is the first work, proposing a differentiable DAG sampling. However, it is not clear whether it has some advantages as some post-processing is still needed if one wants to get better performance. Regarding the time complexity, a thorough analysis of other related work is needed. Moreover, it is suggested to compare to some recent works like the following in their experiments:\n\"DAGs with No Curl: An Efficient DAG Structure Learning Approach\", https://arxiv.org/abs/2106.07197", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bfCiPUiR-8", "reviewer": "Reviewer_oBzg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Following the work of NOTEARS, this paper focuses on the problem of DAG structure learning using gradient-based methods. Existing algorithms, such as NOTEARS and Gran-DAG, require minimizing a differentiable loss function with respect to the graph structure $G$ with an equality constraint $h(G)=0$. This equality constraint holds if and only if $G$ is a DAG. However, to solve this problem, one needs to use the augmented Lagrangian method, which usually requires alternatively solving an inner and an outer problem. As mentioned by the authors, “the augmented Lagrangian optimization is computationally expensive”.\n\nThe main contribution of this work is to propose a differentiable DAG sampling strategy that can be easily implemented with PyTorch or TensorFlow, and this differentiable DAG sampling strategy can ensure that the searching space when solving the optimization problem is exactly the space of DAGs. Thus, the proposed method does not use the augmented Lagrangian method and is more efficient than most of the current methods.\n\nHowever, my major concern is that the proposed method of this paper is only a combination of well-developed techniques. The start point of this paper is Theorem 1, which states that any adjacency matrix of a DAG can be obtained by simultaneously applying row and column-wise permutation to an upper triangular matrix. This result is trivial and has been known for a very long time. Thus, I think it is not appropriate to state it as a theorem. Moreover, Theorem 1 has been applied to sampling DAGs already. In fact, many packages use this result to generate random DAGs. Secondly, to make the sampling procedure differentiable, this paper directly uses the recently developed Gumbel-Softmax, Gumbel-Sinkhorn, and Gumbel-Top-k tricks. Therefore, in my opinion, the idea of separately sampling an upper triangular matrix and a permutation matrix in order to sample a DAG is not novel.\n\nAnother problem is about Equation (3). It would be better to show that the definition of $P({\\bf A})$ is indeed a probability measure.\n\nFinally, in the experiments, the authors used AUC to measure the performance of different methods. This measure might be better than others, but for the completeness of the paper, other commonly used measures should also be included. For example, the ROC curves, SHDs (or SHDs vs. thresholds), and SIDs (or SIDs vs. thresholds).\n\nA minor point: the fourth line of the fourth paragraph on page 3, Thm. 1 -> Th. 1\n", "summary_of_the_paper": "Using the recently developed differentiable sampling techniques for discrete variables (e.g. Gumbel-Softmax) and variable orderings (e.g. Gumbel-Sinkhorn and Gumbel-Top-k), this paper proposes a differentiable DAG sampling strategy, and applies it to the problem of DAG learning.", "summary_of_the_review": "Overall, this paper is well-written. However, the proposed method is only a simple combination of well-developed techniques, and the experiments need to include more metrics. Thus, I think the contributions are only marginally significant or novel.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors proposed an algorithm for sampling DAGs that is suited for continuous optimization. The sampling algorithm has two main steps: In the first step, a causal order over the variables is selected. In the second step, edges are sampled based on the selected order. Moreover, based on this algorithm, they proposed a method in order to learn the causal structure from the observational data. The causal structure learning algorithm is guaranteed to output a DAG at any time and it is not required any pre- or post-processing unlike previous work.

There were concerns by two reviewers on the slight lack of novelty ("the proposed method of this paper is only a combination of well-developed techniques") but I believe the proposed method is still worthwhile. In addition, the paper is overall well written and its experiment evaluation is thorough. It will be a nice addition to the field of differentiable causal discovery.

My recommendation is to accept the paper as a poster.
Decision: Accept (Poster)