Citation and evidence

Directed acyclic graph

18 min full readUpdated 25 references

This article's verification

Report a problem with this article

Edit article
More

Use this article

Raw MarkdownExplore connections

Improve this page

Revision historyDiscuss this article

Topics

AlgorithmsComputer ScienceMachine LearningMathematics

Cite this article

A directed acyclic graph (DAG) is a directed graph that contains no directed cycle: no path that follows the edges in their direction ever returns to the vertex it started from [1]. The structure is also called an acyclic directed graph or an oriented acyclic graph [1]. Every DAG has a topological ordering, a way of lining up its vertices so that all edges point the same way, so the vertices can always be processed with each one coming after everything it depends on [2]. In machine learning DAGs appear in several roles: as the graph of a Bayesian network [3], as the causal diagram in causal inference [3][4], as the computational graph that deep learning frameworks differentiate [5], and as the dependency graph of data and training pipelines [21].

Learning a DAG from data is hard. Finding a high-scoring Bayesian network structure is NP-hard even with large samples, and the number of possible DAGs grows superexponentially with the number of nodes [7][8]. Continuous-optimization methods such as NOTEARS were designed to avoid that combinatorial search [8], and graph neural networks have been built specifically for DAG-shaped inputs [9][10].

Directed graph of eleven numbered nodes with arrows pointing downward and no cycles
An example of a directed acyclic graph: every arrow points downward and no path returns to its starting node. Johannes Rössel, via Wikimedia Commons, Public domain.

Definition and basic properties

A directed graph $G = (V, E)$ consists of a set of vertices $V$ and a set of ordered pairs of vertices $E$, the edges, each written $u \to v$. A directed cycle is a path $v_0 \to v_1 \to \cdots \to v_k$ with $v_k = v_0$. A DAG is a directed graph in which no such path exists [1][2].

Two kinds of vertex are named in every DAG. A source has no incoming edges and a sink has no outgoing edges. Every DAG has at least one source and at least one sink, and it may have many of each: in a graph with $n$ vertices and no edges, every vertex is both [2].

Topological ordering

A topological ordering of a directed graph is a total order of its vertices in which $u$ comes before $v$ for every edge $u \to v$; drawn on a horizontal line, all edges point from left to right [2]. A graph with a directed cycle has no such ordering, because the rightmost vertex of the cycle would need an edge pointing left. Conversely, every DAG has at least one topological ordering, so a directed graph is acyclic exactly when it can be topologically ordered [2]. The ordering need not be unique [11].

Topological sorting can also be described as arranging items "according to a partial order" when some pairs of items are not comparable [12]. Reachability in a DAG supplies that order: one vertex precedes another when a directed path leads from the first to the second. The 2021 DAGNN paper describes this partial ordering as the inductive bias its architecture is built around [10].

Relation to other graphs

Every directed graph, cyclic or not, has an associated DAG. Contracting each strongly connected component (a maximal set of vertices that can all reach one another) to a single vertex yields the strong component graph, also called the condensation, and that graph is always acyclic. A directed graph is itself a DAG if and only if each of its strong components contains a single vertex [2].

Acyclicity can also be read off the adjacency matrix. For a binary adjacency matrix $B \in {0,1}^{d \times d}$, the trace $\operatorname{tr}(B^k)$ counts the closed walks of length $k$ in the graph, so $B$ describes a DAG exactly when $(B^k)_{ii} = 0$ for every vertex $i$ and every $k \geq 1$ [8]. Zheng and colleagues used this fact to show that $B$ is a DAG if and only if $\operatorname{tr}(e^{B}) = d$, where $e^{B}$ is the matrix exponential, a characterization that underlies the NOTEARS method described below [8].

Counting DAGs

The number of DAGs on $n$ labeled vertices is sequence A003024 in the On-Line Encyclopedia of Integer Sequences, whose references include Robert W. Robinson's 1973 chapter "Counting labeled acyclic digraphs" [13]. With $a(0) = 1$, the counts satisfy

a(n)=∑k=1n(−1)k+1(nk) 2k(n−k) a(n−k).a(n) = \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} \, 2^{k(n-k)} \, a(n-k).

Labeled vertices $n$Number of DAGs
11
23
325
4543
529281
63781503
71138779265
8783702329343
91213442454842881

Expanded article table

The counts grow quickly: nine labeled vertices already admit more than $10^{15}$ DAGs [13]. The NOTEARS paper describes the growth as superexponential in the number of nodes [8].

"2.6.1 DAGs: Video", video from MIT OpenCourseWare, published September 12, 2016. Watch on YouTube.

Algorithms on DAGs

Detecting cycles

Whether a directed graph is a DAG can be decided in $O(V + E)$ time with depth-first search. One version computes a postordering of the vertices and checks every edge: if some edge $u \to v$ has $u$ finishing before $v$, the graph contains a directed path from $v$ back to $u$ and therefore a cycle. Another version marks vertices as active while the search is inside them and reports a cycle as soon as it meets an edge into an active vertex [2].

Topological sorting

Two classic algorithms produce a topological ordering in linear time:

AlgorithmIdeaRunning time
Depth-first searchReverse any postordering of the vertices$O(V + E)$ [2]
Kahn's algorithm (1962)Repeatedly remove a source, output it, and lower the in-degree of its out-neighbors$\Theta(V + E)$ with adjacency lists [14]

Expanded article table

The depth-first method works because, in a DAG, every edge $u \to v$ has $u$ finishing after $v$, so reversing the postorder puts every edge in left-to-right order [2]. Kahn's method, published by A. B. Kahn in Communications of the ACM in November 1962 under the title "Topological sorting of large networks", keeps a set of current sources and an in-degree count for each vertex. When a vertex is removed, only its out-neighbors can become new sources. If the set of sources runs out before every vertex has been output, the graph is not a DAG [14][15]. With an adjacency matrix rather than adjacency lists, the same procedure takes $\Theta(V^2)$ time [14].

Longest paths and dynamic programming

Some problems that are hard on general graphs become easy on DAGs. Finding the longest path between two vertices is NP-hard in general directed graphs, but in a DAG it can be computed in linear time by evaluating the recurrence

LLP(v)=max⁡v→w∈E(ℓ(v→w)+LLP(w)),LLP(t)=0,\mathrm{LLP}(v) = \max_{v \to w \in E} \bigl(\ell(v \to w) + \mathrm{LLP}(w)\bigr), \qquad \mathrm{LLP}(t) = 0,

where $\ell$ is the edge weight and $t$ the target vertex, in reverse topological order [2].

The same idea explains dynamic programming in general. The dependency graph of a recurrence, with one vertex per subproblem and an edge from one subproblem to another when evaluating the first requires the second, must be acyclic for the recursion to terminate, and a dynamic programming algorithm evaluates that DAG in reverse topological order so that each subproblem is solved after the subproblems it depends on. Jeff Erickson's Algorithms textbook states it as "every dynamic programming algorithm is equivalent to a postorder traversal of the dependency graph of its underlying recurrence" [2]. Edit distance, subset sum and longest increasing subsequence can all be recast as shortest or longest path problems in such a DAG [2].

DAGs in probabilistic modeling

Bayesian networks

A Bayesian network is a DAG whose vertices are random variables, together with a conditional distribution for each variable given its parents. The graph encodes a factorization of the joint distribution. In Judea Pearl's 1995 Biometrika paper, the factorization is written as

P(x1,…,xn)=∏iP(xi∣pai),P(x_1, \ldots, x_n) = \prod_{i} P(x_i \mid \mathrm{pa}_i),

where $\mathrm{pa}_i$ are the values of the parents of $X_i$ in the graph [3]. Pearl described DAGs as "economical schemes for representing conditional independence assumptions" [3]. The independencies implied by the factorization can be read directly off the graph with the d-separation test. A set of variables $Z$ blocks a path between two variables if the path passes through a vertex where the arrows converge and neither that vertex nor any of its descendants is in $Z$, or through a non-converging vertex that is in $Z$. $Z$ d-separates two sets of vertices when it blocks every path between them, and the conditional independencies implied by the factorization correspond one to one with the d-separation statements of the graph [3].

Causal diagrams

Given a causal reading, the same kind of graph becomes a model of interventions. In Pearl's formulation each variable is determined by its parents and an independent disturbance term,

Xi=fi(pai,εi),i=1,…,n,X_i = f_i(\mathrm{pa}_i, \varepsilon_i), \qquad i = 1, \ldots, n,

and the causal links stand for autonomous physical mechanisms [3]. An external intervention that sets $X_i$ to a fixed value removes the factor $P(x_i \mid \mathrm{pa}_i)$ from the product above; graphically, the arrows into $X_i$ are deleted and the rest of the network is left intact [3].

The paper also sets out the back-door criterion, a graphical test for which covariates to adjust for that Pearl had first presented in 1993 [3]. A set $Z$ satisfies it relative to a treatment $X$ and an outcome $Y$ if no member of $Z$ is a descendant of $X$ and $Z$ blocks every path between $X$ and $Y$ that contains an arrow into $X$. When the criterion holds, the causal effect is identifiable from observational data through the adjustment formula [3]

P(y∣x^)=∑zP(y∣x,z) P(z).P(y \mid \hat{x}) = \sum_{z} P(y \mid x, z) \, P(z).

Causal DAGs have become an established framework for causal inference in epidemiology, often used to choose covariate adjustment sets [16]. A 2021 review in the International Journal of Epidemiology found 234 applied health research articles published between 1999 and 2017 that reported using DAGs, which the review describes as an increasingly popular approach for identifying the confounding variables that need to be conditioned on. The largest DAG in each article averaged 12 nodes, 62% of the articles made at least one DAG available, and 48% reported the adjustment sets their DAGs implied [4]. The authors called the variation in reporting substantial and made recommendations for improving it [4]. DAGitty, a free web application for drawing and analyzing causal DAGs, and its R package can test whether a DAG is consistent with a dataset, enumerate DAGs that are statistically equivalent but causally different, and find adjustment sets that remain valid across them [16].

In machine learning fairness research, counterfactual fairness, proposed by Kusner, Loftus, Russell and Silva at NIPS 2017, builds on a causal model whose graph is assumed to be a DAG. A predictor is counterfactually fair toward an individual if its decision would be the same in a counterfactual world where the individual belonged to a different demographic group [17].

Learning DAGs from data

Structure learning tries to recover the DAG itself from observations. Chickering, Heckerman and Meek showed in 2004 that identifying high-scoring Bayesian network structures is NP-hard even with large samples, and that it stays NP-hard under several restrictions, for example when each node may have at most $k$ parents for any $k \geq 3$ [7]. Classical score-based methods therefore search the combinatorial space of DAGs with heuristics such as greedy search or search over topological orderings [8].

NOTEARS (Zheng, Aragam, Ravikumar and Xing, 2018) replaced the discrete acyclicity constraint with a smooth equation over real weighted adjacency matrices $W \in \mathbb{R}^{d \times d}$. Its main result is that $W$ is a DAG if and only if

h(W)=tr⁡(eW∘W)−d=0,h(W) = \operatorname{tr}\left(e^{W \circ W}\right) - d = 0,

where $\circ$ is the elementwise (Hadamard) product. Squaring the entries makes the matrix nonnegative, so the closed-walk argument above still applies, and $h$ has the simple gradient $\nabla h(W) = \left(e^{W \circ W}\right)^{\top} \circ 2W$ [8]. Structure learning then becomes an equality-constrained continuous optimization problem, which the authors solve for linear structural equation models with a least-squares loss and an $\ell_1$ penalty using standard numerical solvers [8].

DAGs in deep learning

Computational graphs and automatic differentiation

Deep learning frameworks record computations as graphs and differentiate them. PyTorch's autograd tutorial states that autograd keeps a record of tensors and executed operations "in a directed acyclic graph (DAG) consisting of Function objects", in which the leaves are the input tensors and the roots are the output tensors [5]. During the forward pass, autograd runs each operation and stores the operation's gradient function in the DAG; calling .backward() on a root traces the graph back to the leaves, applying the chain rule and accumulating gradients in each leaf tensor's .grad attribute [5]. In PyTorch the DAG is dynamic: after each .backward() call autograd starts a new graph, which is what allows control flow statements inside a model and lets the shape, size and operations change from one iteration to the next [5]. This record is the computational graph behind reverse-mode automatic differentiation and backpropagation; graph execution and eager execution describe the two ways frameworks build and run it.

Not every framework graph is acyclic. TensorFlow represents computation, shared state and the operations that mutate that state as a dataflow graph, and implements loops inside the graph with Switch and Merge primitives [18]. The 2018 EuroSys paper on TensorFlow's dynamic control flow states that the while-loop graph "is cyclic so the result of the loop body can go from one iteration to the next" [19].

Recurrent neural networks are the textbook case of a cyclic description that becomes acyclic in practice. The Deep Learning textbook by Goodfellow, Bengio and Courville describes RNNs as computational graphs that include cycles, and explains that unfolding the recurrence for a finite number of time steps yields an expression that "can now be represented by a traditional directed acyclic computational graph", with one node per variable per time step and parameters shared across steps [6]. Training needs no special algorithm: the gradient is computed by applying ordinary back-propagation to the unrolled graph [6].

The D-VAE paper (NeurIPS 2019) observes that many machine learning models, including neural networks and Bayesian networks, are realized as computations on DAGs [9]. Neural architecture search uses this directly. In DARTS (Liu, Simonyan and Yang, ICLR 2019), the searched building block is a cell defined as "a directed acyclic graph consisting of an ordered sequence of N nodes", where each node is a latent representation such as a feature map, each edge carries an operation, and each intermediate node is computed from all of its predecessors [20]. DARTS relaxes this architecture representation into a continuous one so that the architecture can be searched with gradient descent [20].

Because DAGs are a common input type, researchers have designed graph neural networks specifically for them. D-VAE encodes DAGs with an asynchronous message-passing scheme that follows the computation the DAG represents, rather than the simultaneous message passing used by standard GNNs, and applies the resulting latent space to neural architecture search and Bayesian network structure learning with Bayesian optimization [9]. DAGNN (Thost and Chen, ICLR 2021) processes information in the order defined by the DAG's partial order and was evaluated on source code, neural architectures and probabilistic graphical models [10].

Workflows and data pipelines

Systems that schedule work across many machines commonly describe a job as a DAG of tasks, where an edge means that one task needs another's output.

SystemWhat the vertices areWhat the edges mean
Apache AirflowTasks in a workflowDependencies that set the order and conditions for running tasks [21]
Apache SparkStages of pipelined transformationsDependencies between stages, built from the lineage graph and cut at shuffles [22]
MapReduce, DryadTasks within a jobDependencies tracked for recovery [22]
PyTorch autogradFunction objects (operations)Tensors flowing from inputs to outputs [5]
GitCommit objectsParent links between commits [23]

Expanded article table

Apache Airflow, an open-source workflow orchestrator, names its central concept after the structure. Its documentation defines a Dag as "a model that encapsulates everything needed to execute a workflow": the schedule, the tasks, the dependencies between them and related settings. The Dag is concerned only with how to run the tasks, not with what happens inside them [21]. Airflow was started by Maxime Beauchemin at Airbnb in October 2014, was open source from its first commit, entered the Apache Software Foundation's Incubator in March 2016, and became an Apache Top-Level Project in January 2019 [24].

In Apache Spark, whenever a user runs an action on a resilient distributed dataset (RDD), the scheduler examines the dataset's lineage graph and builds a DAG of stages to execute, pipelining as many narrow transformations as possible inside each stage and cutting stages at the shuffles that wide dependencies require [22]. The RDD paper (NSDI 2012) notes that MapReduce and Dryad likewise track dependencies among a DAG of tasks within a job, though they discard that lineage once the job ends [22].

The same distinction shows up in software for large language model applications. When LangChain introduced LangGraph in January 2024, the announcement noted that chains built with the LangChain Expression Language are directed acyclic graphs, like most data orchestration frameworks, and presented an easy way to add cycles as LangGraph's main contribution, because more complex applications, such as agents, often run a model in a loop so that it can reason about what to do next [25].

Other uses

Version control is a familiar example outside machine learning. Git's glossary defines its commit history as a DAG: commits point to their parents, and no chain of commits begins and ends at the same object [23].

Continue reading

More from See also

More to read

Topics:AlgorithmsComputer ScienceMachine LearningMathematics

References

  1. ^1 ^2 ^3Paul E. Black. "directed acyclic graph". Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, 19 April 2004. xlinux.nist.gov/...directAcycGraph
  2. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^11 ^12Jeff Erickson. "Depth-First Search" (Chapter 6). Algorithms, 1st edition, 2019. jeffe.cs.illinois.edu/...06-dfs.pdf
  3. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9Judea Pearl. "Causal diagrams for empirical research". Biometrika 82(4): 669-688, 1995. doi.org/...82.4.669 (technical report version: ftp.cs.ucla.edu/...R218-B.pdf)
  4. ^1 ^2 ^3Peter W. G. Tennant, Eleanor J. Murray, Kellyn F. Arnold, et al. "Use of directed acyclic graphs (DAGs) to identify confounders in applied health research: review and recommendations". International Journal of Epidemiology 50(2): 620-632, 2021. doi.org/...dyaa213
  5. ^1 ^2 ^3 ^4 ^5PyTorch. "A Gentle Introduction to torch.autograd". PyTorch Tutorials. docs.pytorch.org/...autograd_tutorial
  6. ^1 ^2Ian Goodfellow, Yoshua Bengio and Aaron Courville. "Sequence Modeling: Recurrent and Recursive Nets" (Chapter 10). Deep Learning, MIT Press, 2016. deeplearningbook.org/...rnn
  7. ^1 ^2David Maxwell Chickering, David Heckerman and Christopher Meek. "Large-Sample Learning of Bayesian Networks is NP-Hard". Journal of Machine Learning Research 5: 1287-1330, 2004. jmlr.org/...chickering04a
  8. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8Xun Zheng, Bryon Aragam, Pradeep Ravikumar and Eric P. Xing. "DAGs with NO TEARS: Continuous Optimization for Structure Learning". NIPS 2018 (arXiv:1803.01422). arxiv.org/...1803.01422
  9. ^1 ^2 ^3Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett and Yixin Chen. "D-VAE: A Variational Autoencoder for Directed Acyclic Graphs". NeurIPS 2019 (arXiv:1904.11088). arxiv.org/...1904.11088
  10. ^1 ^2 ^3Veronika Thost and Jie Chen. "Directed Acyclic Graph Neural Networks". ICLR 2021 (arXiv:2101.07965). arxiv.org/...2101.07965
  11. ^NetworkX developers. "topological_sort". NetworkX documentation. networkx.org/...kx.algorithms.dag.topological_sort
  12. ^Paul E. Black. "topological sort". Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, 21 April 2022. xlinux.nist.gov/...topologicalSort
  13. ^1 ^2OEIS Foundation. "A003024: Number of acyclic digraphs (or DAGs) with n labeled nodes". The On-Line Encyclopedia of Integer Sequences. oeis.org/A003024
  14. ^1 ^2 ^3University of Alaska Fairbanks. "CS 411 Fall 2025: Outline & Supplemental Notes for September 19, 2025" (Topological Sort). 19 September 2025. cs.uaf.edu/...lec-20250919-topsort
  15. ^A. B. Kahn. "Topological sorting of large networks". Communications of the ACM 5(11): 558-562, November 1962. doi.org/...368996.369025
  16. ^1 ^2Johannes Textor, Benito van der Zander, Mark S. Gilthorpe, Maciej Liśkiewicz and George T. H. Ellison. "Robust causal inference using directed acyclic graphs: the R package 'dagitty'". International Journal of Epidemiology 45(6): 1887-1894, 2016. doi.org/...dyw341
  17. ^Matt J. Kusner, Joshua R. Loftus, Chris Russell and Ricardo Silva. "Counterfactual Fairness". NIPS 2017 (arXiv:1703.06856). arxiv.org/...1703.06856
  18. ^Martín Abadi, Paul Barham, Jianmin Chen, et al. "TensorFlow: A system for large-scale machine learning". arXiv:1605.08695, 2016. arxiv.org/...1605.08695
  19. ^Yuan Yu, Martín Abadi, Paul Barham, Eugene Brevdo, Mike Burrows, Andy Davis, et al. "Dynamic Control Flow in Large-Scale Machine Learning". EuroSys '18, Porto, April 2018 (arXiv:1805.01772). arxiv.org/...1805.01772
  20. ^1 ^2Hanxiao Liu, Karen Simonyan and Yiming Yang. "DARTS: Differentiable Architecture Search". ICLR 2019 (arXiv:1806.09055). arxiv.org/...1806.09055
  21. ^1 ^2 ^3Apache Software Foundation. "Dags". Apache Airflow documentation (version 3.4.0). airflow.apache.org/...dags
  22. ^1 ^2 ^3 ^4Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker and Ion Stoica. "Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing". NSDI 2012. usenix.org/...nsdi12-final138.pdf
  23. ^1 ^2Git. "gitglossary: A Git Glossary". Git documentation. git-scm.com/...gitglossary
  24. ^Apache Software Foundation. "Project". Apache Airflow documentation. airflow.apache.org/...project
  25. ^The LangChain Team. "LangGraph". LangChain Blog, 17 January 2024. langchain.com/...langgraph

Improve this article

Add missing citations, update stale details, or write a clearer explanation. Anyone can edit: changes go live when you publish, and every edit is checked by an editor.

2 revisions · v2 · 3,529 words · full history

Fact-checks are independent of edits: a reviewer re-verifies the article against its sources and stamps the date. How we verify

Research and drafting on this wiki are AI-assisted, under named human editorial standards. How AI is used here

Reviewer note: Independent fact-check before publication on November 18, 2026: 74 claims checked against 26 cited and independent sources; 1 material and 3 minor corrections applied before publication.

Cite this page: AI Wiki. "Directed acyclic graph." aiwiki.ai, updated 18 Nov 2026, fact-checked 18 Nov 2026. CC BY 4.0. https://aiwiki.ai/wiki/directed_acyclic_graph

Edit article