Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
main_review: Strengths: 
- Contrary to previous work, the proposed method does not pre- or post-processing to make sure the returned graph is DAG.
- It is easy to implement the algorithm in a few lines of code.
- The current work presents a differentiable DAG sampling which I think is novel in this field.

Weaknesses:
- 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. 
- 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.


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:
"DAGs with No Curl: An Efficient DAG Structure Learning Approach", https://arxiv.org/abs/2106.07197
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: _Strengths_
* 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.
* 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.
* 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.
* The paper is clearly written.

_Weaknesses_
* I did not find any obvious weaknesses.

_Questions_
* How many epochs does each method take to converge? In other words, what is the total training time for each method?
* What are the accuracies and speeds for non-differentiable methods?

_Feedback_
* 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.
* Table 2 (bottom left): GraN-DAG is bolded when it should not be.
* 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?

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).
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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”.

The 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.

However, 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.

Another problem is about Equation (3). It would be better to show that the definition of $P({\bf A})$ is indeed a probability measure.

Finally, 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).

A minor point: the fourth line of the fourth paragraph on page 3, Thm. 1 -> Th. 1

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.
review_title: null

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)