Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of learning DAGs from observational data. Different from prior work under the continuous framework, the authors propose an approach to optimize over the polytope of permutations, where edges can be jointly or conditionally optimized given a particular topological ordering. The key to the approach is to leverage recent progress on sparse relaxation methods such as top-k sparsemax and sparseMAP. Some experiments on real data are provided.
strength_and_weaknesses: Strengths: I generally find the approach interesting and a nice mix of ideas from the sparse relaxation literature to the DAG learning problem. The paper is also generally well-written modulo some unspecified notation. 

Weaknesses: The main weakness is the experimental section. Given that this is not a theoretical work, one should at least expect a more comprehensive set of experiments. The work of Reisach et al. (2021) is cited for skipping comprehensive synthetic experiments basically, and both real-world networks experimented on have a small number of nodes. The scaling problem when using OLS has been known for a while for linear regression, and hence the same is expected to happen for linear SEMs, this is why methods such as PC are robust to this problem since PC works by performing CI tests---Reisach et al. (2021). To alleviate the marginal variance problem, one can just use a bit smaller weights for the simulations. It would be great to see how the proposed method behaves against other baselines for ER, SF graphs for different numbers of nodes. Moreover, it is a must to compare the runtimes as well, given that other methods such as NOTEARS do not have a clear computational complexity, it is important to see what the actual performance is in terms of runtime. 

From the experiments, I would like to conclude: Is the proposed method better? Is it faster? Both? I cannot conclude that from the current set of experiments.
clarity,_quality,_novelty_and_reproducibility: Clarity: Most of the paper is clear, but a few wordings for me were confusing. For instance, the term over-relaxation in the introduction is somewhat unclear and to me does not reflect what is said afterwards. In fact, I should bring to the authors' attention a recent work [1] that studies some disadvantages of existing acyclicity regularizers more formally, and perhaps consider referencing it for the next revision. In Section 2, it is stated "the constraint on acyclicity is expressed as a smooth function and then relaxed to allow efficient optimization", what do the authors mean by "relaxed"?

Quality and Novelty: The work in general is of good quality, and although it does not shine in technical contributions, I think the paper nicely leverages work on sparse relaxations for the problem of DAG learning. 

Reproducibility: Authors have shared code for reproducibility so that's a plus, although I have not tested it myself.


[1] Bello et al. (2022) “DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization”. NeurIPS.

summary_of_the_review: My main concerns are on about the experiments, it is not clear if the proposed approach works well for linear/nonlinear models, for different dimensions, and for different types of graphs.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors look at the problem of recovering the DAG structure from samples from a DAG-structured distribution. Despite having seen a lot of important works spanning the last several decades, the problem has remained open and is an active area of research. The proposed solution in this paper consists of two steps i) finding a topological ordering of the DAG, ii) discovering edges according to the ordering. The authors manage to do both steps which is end-to-end on the one hand and accomodates any black-box edge discovery algorithm for step ii).

Experiments conducted by the authors reveal that their algorithm are better in terms of both the metrics SHD and SID. In fact, their solutions learn at the Pareto frontier of these two metrics.
strength_and_weaknesses: Strength: the proposed solution is flexible and more efficient and more accurate than the existing methods. Comparison with the related work has been covered in great detail. The experimental evidence is extensive, consisting of the best algorithms known before and includes both benchmark and synthetic datasets.

Weakness: Ultimately, the paper reads like a conglomeration of existing ideas. I could not clearly find a single new technique that the authors have found.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and clear. The algorithm has a combination of important ideas. The experiments look reproducible to me.
summary_of_the_review: Given the superior experimental performance of the proposed approach, I tend to accept the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper develops a continuous optimization method for learning DAGs by optimizing over the polytope of permutation vectors. Two versions of the methods are provided: (1) alternately iterates between node-ordering and edge-optimization, and (2) optimizes them jointly. The resulting method has several advantages over existing methods, such as (1) returning exact DAGs and (2) accommodating non-differentiable black-box estimators. Experiment results on two real-world datasets are provided.
strength_and_weaknesses: Strength: 
- A new continuous approach to traverse the DAG space is provided. Solving continuous DAG learning task is a topic with significance.
- The approach is flexible and accommodates non-differentiable black-box estimators.

Weakness:
- As the paper mentioned, the possibility of using differentiable approach to learn DAGs via ordering has been proposed by (Cundy et al., 2021; Charpentier et al., 2022). Therefore, the proposed method may seem incremental, i.e., optimizing over permutation vectors instead of permutation matrices as in existing works.
    - I would suggest the authors to provide a detailed discussion of the advantages of their method over (Cundy et al., 2021; Charpentier et al., 2022). Also, can those existing methods be modified to accommodate non-differentiable black-box estimators?
- The paper argued that existing works (Cundy et al., 2021; Charpentier et al., 2022) required expensive optimization over the permutation matrices. However, the paper currently lacks empirical studies to support it--either comparison of running time or scalability to very large graphs would be more compelling to demonstrate the efficiency/scalability of the proposed method.
-  Although the paper mentioned a recent study by Reisach et al. (2021) regarding the flaw of synthetic dataset in DAG learning benchmark, I would still suggest the authors to compare their method to the baselines on those synthetic benchmarks to have an idea about how the method performs. This is because for real world datasets, the model assumption (e.g.,. linear or nonlinear additive noise models) may not hold.
- In 'over-relaxation' part of Section 1, several methods based on penalizing the 'DAG-ness' of the adjacency matrix are actually *guaranteed to return a valid DAG* under some conditions, as shown by the following papers. Therefore the statement is not entirely true and should be corrected.
    - Remark 2 of Ng et al. (2022). On the Convergence of Continuous Constrained Optimization for Structure Learning.
    - Lemma 6 of Bello et al. (2022). DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization.

----------------
I appreciate the detailed response from the authors, which has addressed my concern. I have increased my score accordingly.
clarity,_quality,_novelty_and_reproducibility: The paper is generally clear. The proposed method may be rather incremental compared to existing ones. See above comments for more details.
summary_of_the_review: - The proposed method may be rather incremental compared to existing ones.
- Lack of experiment results on synthetic benchmarks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose a framework for DAG learning from data. The method consists of a two-step procedure, where the first one is based on an observation about optimizing the order of nodes over the permutahedron. Then the edges to keep are selected by using a regularization over the set of functions.
The method is tested on two real-world datasets with promising results.

strength_and_weaknesses: The strengths of the paper are the clarity, the observation of the optimization over the permutahedron, and the fact that it is actually a framework where one can choose different methods for the sub-tasks.
clarity,_quality,_novelty_and_reproducibility: The paper is very well written, the description of the related work is adequate, and the contributions are clear.
As far as I know, the proposed method is novel, producing good results.

The code is included as supplementary material, which is much appreciated for reproducibility.

There seems to be a minor typo in equation (3): the r in the simplex.

summary_of_the_review: The authors of the paper propose an interesting two-step framework for DAG learning, where different methods can be used for the sub-tasks.
It is well written, and the results are promising.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper is in the class of work that suggest using continuous optimisation approaches for DAG learning. The main idea/contribution is leveraging recent approaches in sparse relaxation methods (e.g.,  top-k sparsemax and sparseMAP) for DAG learning. I do not feel that the technical contribution is adequately novel but given the importance of DAG learning in causal inference and Bayesian inference, the paper could be of interest to the learning community.

justification_for_why_not_higher_score: Not a fundamental contribution.
justification_for_why_not_lower_score: The paper could be of interest to the audience given importance of learning DAGs.
Decision: Accept: poster