DAGs with NO TEARS: Continuous Optimization for Structure Learning
Open accessThe DOI matches its DataCite record; 59 of the 60 references it cites were found in a registry or an index.
Abstract
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 \emph{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. Code implementing the proposed algorithm is open-source and publicly available at https://github.com/xunzheng/notears.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Adam: A Method for Stochastic Optimization
Kingma, D. P., & Ba, J. (2014) · arXiv · doi:10.48550/arxiv.1412.6980 · Cited by 98,946
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135 · cited 3×
“Since real-world networks often exhibit scale-free and small-world topologies (Watts and Strogatz, 1998; Barabási and Albert, 1999) with highly connected hub nodes, these kinds of structural assumptions are not only difficult to satisfy, but impossible to check.”
BackgroundMethod(2021) · A First Course in Statistical Programming with R · doi:10.1017/9781108993456.011 · Cited by 13,724
(2006) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/978-0-387-40065-5 · Cited by 9,008
Koller, D., & Friedman, N. (2009) · The MIT Press eBooks · Cited by 7,555
Sparse inverse covariance estimation with the graphical lasso
Friedman, J., Hastie, T., & Tibshirani, R. (2008) · Biostatistics · doi:10.1093/biostatistics/kxm045 · Cited by 6,355
A Limited Memory Algorithm for Bound Constrained Optimization
Byrd, R. H., Lu, P., Nocedal, J., & Zhu, C. (1995) · SIAM Journal on Scientific Computing · doi:10.1137/0916069 · Cited by 6,221
Causation, Prediction, and Search
Spirtes, P., Glymour, C., & Scheines, R. (1993) · Lecture Notes in Statistics · doi:10.1007/978-1-4612-2748-9 · Cited by 4,617
Causation, Prediction, and Search
Spirtes, P., Glymour, C., & Scheines, R. (2001) · doi:10.7551/mitpress/1754.001.0001 · Cited by 4,521
Optimization Methods for Large-Scale Machine Learning
Bottou, L., Curtis, F. E., & Nocedal, J. (2018) · SIAM Review · doi:10.1137/16m1080173 · Cited by 3,128
Smooth minimization of non-smooth functions
Nesterov, Y. (2005) · Mathematical Programming · doi:10.1007/s10107-004-0552-5 · Cited by 2,455
A Linear Non-Gaussian Acyclic Model for Causal Discovery
Shimizu, S., Hoyer, P. O., Hyvärinen, A., & Kerminen, A. (2006) · Cited by 2,231
Optimal Structure Identification with Greedy Search
Chickering, D. M., & Boutilier, C. (n.d.) · Cited by 2,115
Learning Bayesian networks: The combination of knowledge and statistical data
Heckerman, D., Geiger, D., & Chickering, D. M. (1995) · Machine Learning · doi:10.1007/bf00994016 · Cited by 2,017
The max-min hill-climbing Bayesian network structure learning algorithm
Tsamardinos, I., Brown, L. E., & Aliferis, C. F. (2006) · Machine Learning · doi:10.1007/s10994-006-6889-7 · Cited by 1,822
Causal Protein-Signaling Networks Derived from Multiparameter Single-Cell Data
Sachs, K., Perez, O., Pe'er, D., Lauffenburger, D. A., & Nolan, G. P. (2005) · Science · doi:10.1126/science.1105809 · Cited by 1,708
Integrated Systems Approach Identifies Genetic Nodes and Networks in Late-Onset Alzheimer’s Disease
Zhang, B., Gaiteri, C., Bodea, L.-G., Wang, Z., McElwee, J., Podtelezhnikov, A. A., Zhang, C., Xie, T., Tran, L., Dobrin, R., et al. (2013) · Cell · doi:10.1016/j.cell.2013.03.030 · Cited by 1,657
Model selection and estimation in the Gaussian graphical model
Yuan, M., & Lin, Y. (2007) · Biometrika · doi:10.1093/biomet/asm018 · Cited by 1,627 · cited 1×
“Undirected graphical models, also known as Markov networks, is recognized as a convex problem (Yuan and Lin, 2007; Banerjee et al., 2008) nowadays, and hence can be solved using black-box convex optimizers such as CVX (Grant and Boyd, 2014).”
BackgroundBanerjee, O., Ghaoui, L. E., & d’Aspremont, A. (2007) · arXiv (Cornell University) · doi:10.1145/1390681.1390696 · Cited by 1,233
An Algorithm for Fast Recovery of Sparse Causal Graphs
Spirtes, P., & Glymour, C. (1991) · Social Science Computer Review · doi:10.1177/089443939100900106 · Cited by 953
Counting unlabeled acyclic digraphs
Robinson, R. W. (1977) · Lecture Notes in Mathematics · doi:10.1007/bfb0069178 · Cited by 368
A New Scaling and Squaring Algorithm for the Matrix Exponential
Al-Mohy, A. H., & Higham, N. J. (2010) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/09074721x · Cited by 355
Ramsey, J., Glymour, M., Sanchez-Romero, R., & Glymour, C. (2017) · International Journal of Data Science and Analytics · doi:10.1007/s41060-016-0032-z · Cited by 304
Efficient Approximations for the Marginal Likelihood of Bayesian Networks with Hidden Variables
Maxwell Chickering, D., & Heckerman, D. (1997) · Machine Learning · doi:10.1023/a:1007469629108 · Cited by 292
Gámez, J. A., Mateo, J. L., & Puerta, J. M. (2010) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-010-0178-6 · Cited by 275
Schmidt, M., van den Berg, E., Friedlander, M. P., & Murphy, K. P. (2009) · International Conference on Artificial Intelligence and Statistics · Cited by 274
Training Neural Networks Without Gradients: A Scalable ADMM ApproachPreprint
Taylor, G., Burmeister, R., Xu, Z., Singh, B., Patel, A., & Goldstein, T. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.02026 · Cited by 272
Learning graphical model structure using L1-regularization paths
Schmidt, M., Niculescu-Mizil, A., & Murphy, K. J. (2007) · National Conference on Artificial Intelligence · Cited by 230
Bayesian network learning with cutting planesPreprint
Cussens, J. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.3713 · Cited by 210
Learning Causal Bayesian Network Structures From Experimental Data
Ellis, B., & Wong, W. H. (2008) · Journal of the American Statistical Association · doi:10.1198/016214508000000193 · Cited by 183
$\ell_{0}$-penalized maximum likelihood for sparse directed acyclic graphs
van de Geer, S., & Bühlmann, P. (2013) · The Annals of Statistics · doi:10.1214/13-aos1085 · Cited by 168
Probabilistic network construction using the minimum description length principle
Bouckaert, R. R. (2005) · Lecture Notes in Computer Science · doi:10.1007/bfb0028180 · Cited by 161
QUIC: quadratic approximation for sparse inverse covariance estimation
Hsieh, C., Sustik, M. A., Dhillon, I. S., & Ravikumar, P. (2014) · Journal of Machine Learning Research · Cited by 146
Self-citationLearning Bayesian networks with thousands of variables
Scanagatta, M., de Campos, C. P., Corani, G., & Zaffalon, M. (2015) · Research Portal (Queen's University Belfast) · Cited by 140
Finding optimal Bayesian networks by dynamic programming
Singh, A. P., & Moore, A. (2018) · KiltHub Repository · doi:10.1184/r1/6605669 · Cited by 123
High-dimensional learning of linear causal networks via inverse covariance estimationPreprint
Loh, P., & Bühlmann, P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.3492 · Cited by 103
Fu, F., & Zhou, Q. (2012) · Journal of the American Statistical Association · doi:10.1080/01621459.2012.754359 · Cited by 103
Practical Gauss-Newton Optimisation for Deep Learning
Botev, A., Ritter, H., & Barber, D. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.03662 · Cited by 96
Addendum on the scoring of Gaussian directed acyclic graphical models
Kuipers, J., Moffa, G., & Heckerman, D. E. (2014) · The Annals of Statistics · doi:10.1214/14-aos1217 · Cited by 92
Concave penalized estimation of sparse Gaussian Bayesian networks
AragamBryon, & Zhouqing (2015) · Journal of Machine Learning Research · doi:10.5555/2789272.2886822 · Cited by 89
Learning Bayesian Networks is NP-Complete
Chickering, M. (1996) · Cited by 87
Concave Penalized Estimation of Sparse Gaussian Bayesian NetworksPreprint
Aragam, B., & Zhou, Q. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1401.0852 · Cited by 79
Self-citationOn the number of cycles in a graph
Harary, F., & Manvel, B. (1971) · Czech digital mathematics library · Cited by 70
Machine Learning of Bayesian Networks Using Constraint Programming
van Beek, P., & Hoffmann, H.-F. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-23219-5_31 · Cited by 65
Structure discovery in Bayesian networks by sampling partial orders
Niinimäki, T., Parviainen, P., & Koivisto, M. (2016) · Aaltodoc (Aalto University) · doi:10.5555/2946645.2946702 · Cited by 60
Learning Bayesian networks with ancestral constraints
Chen, E. Y.-J., Shen, Y., Choi, A., & Darwiche, A. Y. (2016) · neural information processing systems · Cited by 56
A* Lasso for Learning a Sparse Bayesian Network Structure for Continuous Variables
Xiang, J., & Kim, S. Y. (2013) · neural information processing systems · Cited by 51
Finding optimal gene networks using biological constraints.
Ott, S., & Miyano, S. (2003) · PubMed · Cited by 48
Learning Directed Acyclic Graphs with Penalized Neighbourhood RegressionPreprint
Aragam, B., Amini, A. A., & Zhou, Q. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.08963 · Cited by 48
Self-citationThresholding Procedures for High Dimensional Variable Selection and Statistical Estimation
Zhou, S. (2010) · Cited by 45
Polyhedral aspects of score equivalence in Bayesian network structure learning
Cussens, J., Haws, D., & Studený, M. (2016) · Mathematical Programming · doi:10.1007/s10107-016-1087-2 · Cited by 45
Multi-Domain Sampling With Applications to Structural Inference of Bayesian Networks
Zhou, Q. (2011) · Journal of the American Statistical Association · doi:10.1198/jasa.2011.ap10346 · Cited by 39
Thresholding procedures for high dimensional variable selection and statistical estimation. NIPS
Zhou, S. (n.d.) · Cited by 38
Penalized estimation of directed acyclic graphs from discrete data
Gu, J., Fu, F., & Zhou, Q. (2018) · Statistics and Computing · doi:10.1007/s11222-018-9801-y · Cited by 36
Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables
Scanagatta, M., Giorgio Corani, A., de Campos, C. P., & Zaffalon, M. (2016) · Research Portal (Queen's University Belfast) · Cited by 29
Proximal Quasi-Newton for Computationally Intensive L1-regularized M-estimatorsPreprint
Zhong, K., Yen, I. E. H., Dhillon, I. S., & Ravikumar, P. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1406.7321 · Cited by 23
Self-citationNo penalty no tears: Least squares in high-dimensional linear modelsPreprint
Wang, X., Dunson, D. B., & Leng, C. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.02222 · Cited by 13
Optimization Methods for Large-Scale Machine Learning
Bottou, L., Curtis, F. E., & Nocedal, J. (2016) · arXiv · doi:10.48550/arxiv.1606.04838
Research works printed but not linked: 5
- O. Bousquet and L. Bottou. The tradeoffs of large scale learning. In Advances in neural information processing systems, pages 161-168, 2008.
- D. M. Chickering, D. Heckerman, and C. Meek. Large-sample learning of Bayesian networks is NP-hard. Journal of Machine Learning Research, 5:1287-1330, 2004.
- D. Koller and N. Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
- T. Silander and P. Myllymaki. A simple approach for finding the globally optimal bayesian network structure. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, 2006.
- M. Teyssier and D. Koller. Ordering-based search: A simple and effective algorithm for learning bayesian networks. In Uncertainty in Artifical Intelligence (UAI), 2005.
Cited by
DAG-GNN: DAG Structure Learning with Graph Neural NetworksPreprint
Yu, Y., Chen, J., Gao, T., & Yu, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1904.10098 · Cited by 728
A survey of Bayesian Network structure learning
Kitson, N. K., Constantinou, A. C., Guo, Z., Liu, Y., & Chobtham, K. (2023) · Artificial Intelligence Review · doi:10.1007/s10462-022-10351-w · Cited by 379
Causal Machine Learning: A Survey and Open Problems
Kaddour, J., Lynch, A., Liu, Q., Kusner, M. J., & Silva, R. (2025) · Foundations and Trends® in Optimization · doi:10.1561/2400000052 · Cited by 353
Gradient-Based Neural DAG LearningPreprint
Lachapelle, S., Brouillard, P., Deleu, T., & Lacoste-Julien, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.02226 · Cited by 326
Differentiable Causal Discovery from Interventional DataPreprint
Brouillard, P., Lachapelle, S., Lacoste, A., Lacoste-Julien, S., & Drouin, A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.01754 · Cited by 293
Metadata
- Authors
- Zheng, X., Aragam, B., Ravikumar, P., & Xing, E. P.
- Affiliations
- Carnegie Mellon University (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2018
- Volume
- 31
- Pages
- 9472-9483
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1803.01422
- OpenAlex
- W2889900103
- Cited by
- 1,700
- References
- 60
- Citations by year
- 2026: 527 · 2025: 357 · 2024: 268 · 2023: 250 · 2022: 128 · 2021: 97 · 2020: 52 · 2019: 19 · 2018: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- neural information processing systems
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Modeling and Causal Inference
- Physical Sciences › Mathematics › Statistics and Probability › Statistical Methods and Inference
- Physical Sciences › Computer Science › Artificial Intelligence › Gaussian Processes and Bayesian Inference
- Keywords
- directed acyclic graphs, Bayesian network structure learning, acyclicity constraints, continuous optimization, graph structure estimation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.