We propose a novel score-based approach to learning a directed acyclic graph (DAG) from observational data. We adapt a recently proposed continuous constrained optimization formulation to allow for nonlinear relationships between variables using neural networks. This extension allows to model complex interactions while avoiding the combinatorial nature of the problem. In addition to comparing our method to existing continuous optimization methods, we provide missing empirical comparisons to nonlinear greedy search methods. On both synthetic and real-world data sets, this new method outperforms current continuous methods on most tasks, while being competitive with existing greedy search methods on important metrics for causal inference.
################## Response to rebuttal ##################
I would like to thank the authors for their diligent rebuttal. Overall, I consider that the issues raised in my review have been mostly addressed. 
In summary, after reading the other reviews and going through the revised manuscript, I believe the paper would be a meaningful contribution to the field, both in terms of the potential applicability of GraN-DAG to certain problems and its potential to lead to future work. As a result, I have updated my score to support acceptance without reservations.
In particular, the authors now discuss clearly some of the potential limitations of the approach, such as the scaling of its asymptotic complexity with respect to the number of features or its statistical performance in the small sample size regime. The additional experimental results are, in my opinion, also a good addition to the manuscript, further clarifying the strengths and weaknesses of NOTEARS, CAM and GraN-DAG under different regimes and modelling assumptions. I believe these changes substantially improve the paper, as it will both help practitioners decide when to use GraN-DAG as well as clearly delineate avenues for future work.
# Minor points / additional questions
The new results regarding convergence in Table 4 suggest that early stopping might indeed be instrumental. I wonder the extent to which NOTEARS could benefit from early stopping, be it in terms of runtime or, less likely due to its use of explicit regularization, the quality of the structures it retrieves. 
# Typos
Section 3.6: … GraN-DAG performs fewer iteration(s) than NOTEARS…
Section 5: GraN-DAGand DAG-GNN -was- were not designed with…
Appendix A.1: … graphs can be roughly -halfed- halved when executed…
Appendix A.5: … graphs were generated using the -BarabsiAlbert- Barabási-Albert model …
Appendix A.9: … to selecting hyperparameters in practice consist(s) in ...
################## Original review ##################
# High-level assessment
The manuscript presents an alternative to the method in [2] to extend the ideas of [1] to nonlinear DGMs using neural networks. 
From a methodological perspective, in my opinion the proposed approach is sound and sufficiently novel to be a significant contribution. While some limitations might be present, such as being prone to overfitting without relying on additional (pre/post)-processing heuristics or perhaps being computationally intensive for high-dimensional data ($O(p^{3})$ runtime per SGD step), I believe that addressing those issues (if indeed present) could be left for future work.
The paper is written clearly, being easy-to-follow while providing enough detail to understand the proposed method in depth and attempt to reproduce the results.
In my opinion, perhaps the weakest aspect of the paper concerns the experimental analysis, which is somewhat limited in its scope. Most notably, I believe the current experimental setup focuses on cases likely to be favorable to the proposed approach relative to the baselines ($n > p$, nonlinear and non-additive ground-truth models) while presenting no results for other settings commonly encountered in structure learning applications, such as high-dimensional $n << p$ problems or ground-truth models given by linear or generalized linear SCMs.
Taking all those factors into consideration, I currently lean towards a “weak accept” rating, but would gladly modify my score after the author discussion phase as appropriate.
# Summary
In this paper, the authors propose a novel approach for learning the structure of Directed Graphical Models (DGMs) from observational data that allows to flexibly model nonlinear relationships between variables using neural networks.
The proposed method builds on the recent breakthrough in [1], which pioneered the use of a smooth characterization of acyclicity for directed graphs. In particular, the authors in [1] use this characterization to learn the structure of **linear** DGMs by solving a (nonconvex) continuous, constrained optimization problem.
The main contribution of this manuscript is an extension of the approach in [1] to the nonlinear setting by making use of neural networks, and which appears to outperform the only existing method that shares a similar high-level goal [2], presumably by allowing more flexibility in its parametrization.
In a nutshell, the authors accomplish this by:
1. Flexibly modelling the conditional distribution of each variable $X_{j}$ as a nonlinear function of (possibly) all other variables $\bf{X_{-j}}$ using an MLP, i.e. $p_{j}(X_{j} \mid \bf{X_{-j}}) = f_{j}(X_{j} ; NN_{j}(\bf{X_{-j}}))$, with $f_{j}$ denoting any probability density differentiable w.r.t. its parameters and $NN_{j}$ being a neural network with parameters $\theta_{j}$.
2. Deriving a function $C_{i,j}(\theta_{j})$ such that $C_{i,j}(\theta_{j}) = 0$ is a sufficient condition for the conditional distribution of $X_{j}$ to be independent of $X_{i}$.
3. Using $C_{i,j}(\theta_{j})$, which is differentiable w.r.t. $\theta_{j}$ for most values of $\theta_{j}$, to define a “connectivity” matrix to be directly plugged into the acyclicity criterion in [1].
4. Following [1], the model is then fit by (constrained) maximum likelihood using an augmented Lagrangian method. However, unlike [1], the unconstrained subproblem in each iteration of the augmented Lagrangian method is solved using stochastic gradient descent, rather than a batch quasi-Newton method, and regularized using early stopping on an external validation set, rather than by using explicit $L_{1}$ regularization to induce sparsity.
5. The authors also incorporate additional “heuristics”, such as borrowing the Preliminary Neighbour Selection (PNS) and feature selection pruning techniques from [3], which are reported to greatly enhance the performance of the proposed approach (Table 4), and adapt the thresholding scheme in [1] to the nonlinear setting.
The proposed method is evaluated using synthetic and semi-synthetic data, as well as one real-world dataset.  The results suggest that, in low dimensional problems ($n > p$, $p \le 100$) for which the ground-truth relationships between variables are nonlinear and non-additive, the proposed approach clearly outperforms [2] and also outperforms [3] in many settings, albeit often not by a statistically significant margin in the latter case.
# Major points / suggestions
1. I believe it could be argued that one of the main drawbacks of the smooth acyclicity constraint in [1] is its high computational complexity w.r.t. the number of features. However, [1] uses a batch quasi-Newton method to solve the unconstrained subproblems in their optimization routine, which should in principle lead to relatively few $O(p^3)$ matrix exponential evaluations being necessary. 
As it relies on the same characterization of acyclicity as [1], this drawback might also limit the scalability of the proposed approach for high-dimensional data. Moreover, since the method in this manuscript uses mini-batch gradient descent instead, this problem could in fact be exacerbated by perhaps requiring substantially more $O(p^3)$ matrix exponential evaluations.
To this end, I would be glad if the authors could clarify whether this could indeed be a limitation or not. In any case, I believe it could also be helpful to include a small discussion regarding computational complexity for the proposed approach and related work in the manuscript or appendix.
2. All experimental results reported in the manuscript use only data generation models with nonlinear and non-additive relationships between variables.
This setup is well aligned with the contribution, as it emphasises its ability to flexibly model nonlinear relationships between variables learnt using global, gradient-based optimization. In contrast, most baselines are limited to either linear/generalized linear models or use some variant of greedy search.
While investigating this setting is certainly the main priority given the problem statement, I believe it would also be important to characterize the extent to which the performance of the proposed approach deteriorates when this extra flexibility is not needed, if at all. To this end, I would encourage the authors to repeat their experiments for synthetic data, but generated under linear and generalized linear SCMs.
In particular, it is remarkable that CAM [3], which suffers from model misspecification due assuming the data is generated by a generalized linear model, remains so competitive throughout all experiments shown in the current version of the manuscript. It would be interesting to see if the proposed approach can match or still outperform CAM under CAM’s “ideal scenario”.
3. Parallel to the previous point, all experimental results in the manuscript so far concern somewhat low-dimensional data $p \le 100$ and relatively abundant data $n \approx 1,000 > p$.
This setup might also be well aligned with the proposed approach, which could be more prone to overfitting than some of the baselines due to its high capacity and its lack of explicit sparsity-inducing regularization, which was found to boost performance for NOTEARS [1, Fig. 3(b)]. 
Also, in the small sample size regime, the reliance on an external validation set for early stopping might become a liability by (i) reducing the amount of data available for model fitting and (ii) making the fitted DGMs less stable w.r.t. changes in the random seed which, compounded with the nonconvexity of the objective, could be problematic if the DGM is to be interpreted for downstream tasks (e.g. in computational biology).
To this end, I would likewise encourage the authors to extend their experimental setup for synthetic data by (i) repeating their experiments for one “high-dimensional” setting ($n << p$) and (ii) studying the stability of the DAG w.r.t. different training runs.
4. All experimental results currently focus heavily on accuracy, while the computational aspect of the problem is largely secondary.
To this end, it would be interesting to study, using synthetic data, the scalability of the proposed approach relative to the best performing baseline approaches with respect to (i) number of features, (ii) sparsity of the ground-truth DGM and (iii) sample size, covering a sufficiently broad range in each case (low-dimensional vs high-dimensional, sparse vs dense, scarce vs abundant sample size).
# Minor points / suggestions
1. Perhaps the decision to permanently set the thresholding masks to 0 when an entry of the connectivity matrix is “small enough” could be justified further. For example, by showing that this heuristic rarely “zeros out” incorrectly any entries, or that such entries would seldom become nonzero again if the model was trained for longer without being masked.
2. I might have missed it, but I could not find the info about how the train/validation split is formed for the experiments following Section A.1.
# References
[1] Zheng, Xun, et al. "DAGs with no tears: Continuous optimization for structure learning." *Advances in Neural Information Processing Systems*. 2018.
[2] Yu, Yue, et al. "DAG-GNN: DAG Structure Learning with Graph Neural Networks." *International Conference on Machine Learning*. 2019.
[3] Bühlmann, Peter, Jonas Peters, and Jan Ernest. "CAM: Causal additive models, high-dimensional order search and penalized regression." *The Annals of Statistics* 42.6 (2014): 2526-2556.