CoChat

DAGs with NO TEARS: Continuous Optimization for Structure Learning

Open access

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

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1803.01422

Cites

59 of 59 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Research works printed but not linked: 5

  1. O. Bousquet and L. Bottou. The tradeoffs of large scale learning. In Advances in neural information processing systems, pages 161-168, 2008.
  2. 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.
  3. D. Koller and N. Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
  4. 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.
  5. 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

See all 1,700

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