DAGs with NO TEARS: Continuous Optimization for Structure Learning
Estimating the structure of directed acyclic graphs (DAGs, also known as Bayesian networks) is a challenging problem since the search space of DAGs is combinatorial and scales superexponentially with the number of nodes. Existing approaches rely on various local heuristics for enforcing the acyclicity constraint. In this paper, we introduce a fundamentally different strategy: we formulate the structure learning problem as a purely continuous optimization problem over real matrices that avoids this combinatorial constraint entirely. This is achieved by a novel characterization of acyclicity that is not only smooth but also exact. The resulting problem can be efficiently solved by standard numerical algorithms, which also makes implementation effortless. The proposed method outperforms existing ones, without imposing any structural assumptions on the graph such as bounded treewidth or in-degree.
The authors study the problem of structure learning for Bayesian networks. The conventional methods for this task include the constraint-based methods or the score-based methods which involve optimizing a discrete score function over the set of DAGs with a combinatorial constraint. Unlike the existing approaches, the authors propose formulating the problem as a continuous optimization problem over real matrices, which performs a global search, and can be solved using standard numerical algorithms. The main idea in this work is using a smooth function for expressing an equality constraint to force acyclicity on the estimated structure. The paper is very well written and enjoyable to read. I have the following comments:  - Least-Squares loss is used in this work as the score function. It seems that the main reason for this choice is its desirability from the optimization point of view. I was wondering if there are any structure related guarantee when using this score function. For example, will the global optimum be in the Markov equivalence class of the ground truth DAG? Will we be able to detect the v-structures?, etc.  - Two restricting assumptions in this work are linearity and the assumption of full observability. Both of these assumptions are perfectly reasonable for this stage of the research, but I was wondering if the authors have examined their approach on models which are violating these assumptions? Specifically, in the case of non-linear SEM, how would be the output related to the ground truth DAG? Or more importantly, how essential is additive noise for the performance of Least-Squares loss?  - Augmented Lagrangian method is used for solving the equality-constrained program. My concern is that in this method, the penalty term may force some sparsity restrictions on the learned structure. This may prevent the proposed approach from working well for all desired levels of sparsity.  - The main technical tool in this work is the use of function h(.) for characterizing acyclicity. This characterization seems to be new in the literature, but it would be a more clarifying if the authors mention that the connection between the trace of the powers of the adjacency matrix and cycles in the corresponding graph was known in the literature (for example, Frank Harary, Bennet Manvel "On the number of cycles in a graph," 1971).  My concern about the function h(.) is regarding property (b) of function: "The values of h quantify the “DAG-ness” of the graph". I am not sure how true this claim is: First of all, the value of h depends on the edge weights in the graph. Therefore, two graphs with exactly same structure but different weights will get different values for h(W). This gets more problematic as we can design a graph with more cycles, but smaller weights and end up getting a lower value for h compared to another graph with fewer cycles but larger weights.  - Another concern of mine regarding function h(.) is that it over counts the cycles: If there is just one loop (cycle of length 1) in the graph, its effect will appear in all powers of the adjacency matrix. Also, if there is a cycle of length 3 in the graph, it will cause a non-zero value for all of its three corresponding vertices on the diagonal of W^3. In line 422 in the supplementary materials, it is mentioned that tr(B+B^2+...) counts the number of cycles in B. Based on the aforementioned examples, can we say that this sentence is not necessarily true? A clarification in this regard would be appreciated.  - I suspect that for small values of coefficients, specifically, if all were less than 1, for example, w_{ij}~unif([0.1 0.5]) the error of the proposed method will increase. This is due to the fact that h(w) will be small and the algorithm may make more errors. It would be appreciated if the authors also examine their proposed method on such values.  - The simulations and experiments are sufficient and seem fair.   -----After author feedback:   I thank the authors for their responses. Based on the responses, I increase my score to 8. However, I still have concerns regarding the used score function, the properties of function h(.), and the performance on real data.