betaFeedback

WorksMathematics

Interpretable confidence regions for causal discovery

Abstract

Most work in causal discovery focuses on point estimation of the underlying causal graph, while uncertainty in the learned structure has received substantially less attention. We develop confidence regions for the completed partially directed acyclic graph (CPDAG) identified from observational data. Our approach builds on perturbed PC (Chang et al., 2026), which generates plausible CPDAGs by perturbing the conditional independence tests underlying the widely used PC algorithm. The threshold used in these tests controls how perturbations translate into variation across the resulting CPDAGs. We propose a new thresholding strategy that suppresses spurious variation across runs while preserving asymptotic coverage, producing a substantially tighter collection of plausible CPDAGs. This collection is summarized through confidence balls and model confidence intervals constructed from the partially ordered set of CPDAGs under model inclusion. We also develop new theory and algorithms for the exact computation of these regions. Simulations show that our confidence regions attain good coverage while being substantially smaller and more interpretable than the original perturbed PC collections.

Introduction

A directed acyclic graph (DAG) provides an interpretable representation of causal relationships among a set of variables. Nodes represent variables, while directed edges represent direct causal relationships. The DAG also encodes conditional independence relationships implied by the causal structure ([38, 39, 48]). Causal DAGs have been used in many scientific applications, including genomics and molecular biology ([15, 44]), neuroscience ([46]), epidemiology ([18, 21]), and climate science ([43]).

In practice, the underlying DAG is typically unknown and must be learned from data, a task known as causal discovery. Observational data generally identify only a Markov equivalence class of DAGs rather than a unique DAG. A completed partially directed acyclic graph (CPDAG) represents this equivalence class, with directed edges for identifiable orientations and undirected edges for unresolved ones ([56]). Thus, causal discovery from observational data often targets the CPDAG.

A large body of work focuses on obtaining point estimates of the underlying CPDAG. Constraint-based methods, most prominently the PC algorithm and its variants, recover the graph through conditional independence testing ([8, 19, 24, 40, 48]). Score-based methods instead optimize a score over DAGs or Markov equivalence classes, with prominent examples including greedy equivalence search and its variants ([6, 7, 22]), as well as exact search methods based on dynamic programming and shortest-path search ([45, 62]). Hybrid methods combine constraint-based screening with score-based search ([35, 54]). Other score-based approaches formulate this optimization problem explicitly using linear or integer programming ([3, 10, 11, 23, 28, 31 Xu et al.,] 2025, Zhang et al. [64], or continuous optimization (Yu et al., 2019, Zheng et al., [65]). See Glymour et al. [16] for a broader review of causal discovery methods.

Despite this extensive literature on point estimation, quantifying uncertainty in the learned graph remains relatively understudied. Causal discovery procedures can be pointwise consistent but not uniformly consistent under the usual Markov and faithfulness assumptions (Robins et al., [41], Zhang and Spirtes, [63]). Uniform guarantees require stronger separation conditions, such as strong faithfulness, that rule out distributions arbitrarily close to unfaithfulness but can be highly restrictive in practice (Sondhi and Shojaie, [47], Uhler et al., [55]). A single estimated graph may therefore mask substantial uncertainty about the underlying causal structure, motivating confidence regions with formal coverage guarantees.

Several approaches quantify uncertainty in graphical structure. Bayesian methods retain collections of high posterior graphical models (Friedman et al., [13], Friedman and Koller, [14], Kuipers and Moffa, [29], Niinimaki et al., [36]), but these summaries depend on the prior and model specification and do not provide frequentist coverage guarantees for the underlying graph. Frequentist approaches have largely focused on confidence regions for causal effects that account for uncertainty in the underlying causal structure (Strieder and Drton, [49, 50], Strieder et al., [51]). Relatedly, Gradu et al. [17] develop post-selection inference for a causal effect defined relative to the selected graph rather than the true graph. More directly related to structural uncertainty, Wang et al. [57] construct confidence sets for causal orderings and summarize them through lower and upper bounds on ancestral relations. Their analysis assumes that the underlying DAG is identifiable. None of these works construct frequentist confidence regions with coverage guarantees for the true CPDAG.

The perturbed PC procedure of Chang et al. [4], which we build on in this paper, generates a collection of plausible CPDAGs with asymptotic coverage guarantees. The procedure constructs this collection by repeatedly perturbing the conditional independence tests used by PC. Each perturbed test compares a noisy Fisher-transformed sample partial correlation with a threshold to decide whether to reject conditional independence. In the original method, the CPDAG collection serves primarily as an intermediate object for constructing confidence intervals for causal effects rather than as a direct summary of structural uncertainty. Our focus is different: we study the CPDAG collection itself and seek confidence regions that provide coverage for the true CPDAG while remaining compact and interpretable. This shift in focus requires controlling spurious variation across the entire collection while still retaining runs that detect weak signals.

Our contributions

We first provide a theoretical analysis of perturbed PC across different thresholds, perturbation scales, and numbers of resamples. The threshold of Chang et al. [4] is of order log⁡n/M\log n/M, where nn is the sample size and MM is the number of perturbed runs, so it decreases as MM grows. This decreasing threshold helps weak signals survive in at least one run, but it also allows increasingly extreme null statistics to pass the threshold. Our proposed threshold instead grows on the order of log⁡M\sqrt{\log M}, matching the scale of the largest perturbations under the null. This larger threshold filters out most null statistics across runs while still allowing weak nonzero signals to pass in at least one run. This tradeoff preserves asymptotic coverage without requiring a signal strength condition such as strong faithfulness and produces substantially tighter CPDAG collections.

We next develop interpretable summaries of the perturbed PC collection. A large collection of plausible CPDAGs can be difficult to interpret directly, so we seek regions that capture their structural extent in a concise form. We exploit the partially ordered set (poset) of CPDAGs under model inclusion for this purpose. The poset induces a shortest path distance, which we use to construct confidence balls centered at the original PC estimate with radius chosen to contain the collection. Its order structure also defines confidence intervals through common lower and upper CPDAGs that bound every graph in the collection. These regions provide concise and interpretable summaries of structural uncertainty while retaining the coverage of the underlying collection.

Finally, we develop new computational theory for constructing both confidence balls and intervals. The confidence ball calculations rely on the shortest path distance, for which we derive stronger lower and upper bounds than those in Taeb et al. [53]. We also show that the distance decomposes exactly across disconnected components, reducing large shortest path problems to smaller ones. For polytrees, we obtain an exact characterization that substantially simplifies the shortest path search. These structural results also sharpen the bounds and search procedures for general pairs of CPDAGs, even when the graphs are neither disconnected nor polytrees. The confidence interval calculations require common lower and upper CPDAGs, for which we derive new bounds. Together with new restrictions on shortest paths, these results substantially reduce the search space and speed up exact computation. These tools are motivated by confidence region construction but apply more broadly to CPDAG comparison, including benchmarking causal discovery methods and sensitivity analysis.

We illustrate our approach in a synthetic experiment with p=10p = 10 variables. We generate 20 distinct linear Gaussian structural equation models (SEMs), each defined on an independently sampled random DAG with expected degree two, and simulate 30 independent datasets from each SEM. See § 7 for details on the setup. The resulting 600 datasets are analyzed over a range of sample sizes nn using perturbed PC with M=1000M = 1000 runs. As a benchmark, we use the perturbed PC collection of Chang et al. [4]. We construct confidence balls from both this collection and the collection obtained using our proposed threshold. We compare the coverage of these regions with that of the Chang et al. [4] collection and the PC point estimate. We also report the ball radius. Figure 1 shows the results.

Empirical confidence ball coverage and mean ball radius

Figure 1. Empirical confidence ball coverage (left) and mean ball radius (right) for a synthetic setting with p=10p = 10. Results are obtained over 600 instances. The data generating setup is described in § 7.

The PC point estimate has poor coverage, as expected when structural uncertainty is ignored. The collection of Chang et al. [4] improves coverage but undercovers at small sample sizes, while converting this collection into a confidence ball substantially improves coverage. The main advantage of our proposed threshold is a substantial reduction in radius while maintaining comparable coverage. The larger threshold suppresses more spurious null rejections across perturbed runs, reducing variation in the retained CPDAG collection and producing substantially smaller confidence balls. More broadly, confidence balls and model confidence intervals replace a large unstructured collection of plausible CPDAGs with a compact structural summary, given by a center and radius or by lower and upper graph bounds, and can further improve coverage in more difficult settings; see § 7.

The rest of the paper is organized as follows. § 2 reviews CPDAGs and the CPDAG poset. § 3 defines confidence balls and intervals. § 4 analyzes the generalized perturbed PC procedure and constructs the regions. § 5 develops bounds and exact results for the required computations, and § 6 assembles them into search procedures. § 7 and § 8 report simulations on the confidence regions and on computational performance.

Background

Graphical preliminaries

We consider graphs with nodes representing random variables and edges between them representing probabilistic dependencies between these variables. Core graphical concepts are described below.

Node, edge, subgraph, cycle

A graph G=(V,E)\mathcal{G} = (V, E) consists of a finite set of vertices VV and a set of edges EE. We consider two types of edges: directed (u→v)(u \to v) and undirected (u−v)(u - v). The skeleton of G\mathcal{G}, denoted Skel⁡(G)\operatorname{Skel}(\mathcal{G}), is the undirected graph obtained by replacing all directed edges in G\mathcal{G} with undirected edges. A graph G′=(V,E′)\mathcal{G}' = (V, E') is a subgraph of G=(V,E)\mathcal{G} = (V, E) if E′⊆EE' \subseteq E. A cycle is a sequence of distinct vertices v1,…,vkv_1, \ldots, v_k (k≥3k \ge3) such that there is an edge between every two adjacent vertices in the sequence and between vkv_k and v1v_1. A directed cycle is a cycle where all edges are directed v1→v2→⋯→vk→v1v_1 \to v_2 \to\cdots\to v_k \to v_1.

Directed acyclic graphs (DAGs)

A directed acyclic graph (DAG) is a graph containing only directed edges and no directed cycles. For a DAG D\mathcal{D}, let Pa⁡D(v)\operatorname{Pa}_{\mathcal{D}}(v) denote the set of parents of vertex vv, i.e., {u∈V∣u→v∈E}\{u \in V \mid u \to v \in E\}. A triple of vertices (u,v,w)(u, v, w) forms a vv-structure (or unshielded collider) if u→v←wu \to v \leftarrow w exists in the graph and there is no edge between uu and ww. DAGs can be interpreted as probabilistic models via a concept known as d-separation Drton and Maathuis [12], Pearl [37], which provides a graphical criterion for determining conditional independence relationships implied by the graph.

Completed partially directed acyclic graphs (CPDAGs)

Different DAGs can encode the same conditional independencies; see Figure 2. As such, from observational data alone, a DAG is only identifiable up to a Markov equivalence class. Two DAGs are Markov equivalent if and only if they possess the same skeleton and the same set of v-structures Andersson et al. [1], Verma and Pearl [56]. Each equivalence class can be uniquely represented by a completed partially directed acyclic graph (CPDAG), which has directed edges where all DAGs in the class agree and undirected edges where the direction is not identifiable. The skeleton of a CPDAG G\mathcal{G}, denoted Skel⁡(G)\operatorname{Skel}(\mathcal{G}), is the undirected graph obtained by replacing all directed edges with undirected edges.

Example CPDAG representing DAGs and Markov equivalent DAGs

Figure 2. Example CPDAG representing DAGs in the same equivalence class. These DAGs have the same skeleton and same v-structures, and thus encode the same conditional independence (CI) statements. We also present a DAG in the right that does not have the same v-structure as the remaining and is hence not Markov equivalent with the others.

CPDAGs as both graphs and models

A CPDAG represents a Markov equivalence class of DAGs and therefore encodes a set of conditional independence relationships. We associate each CPDAG with the statistical model consisting of distributions that satisfy these relationships.

Let VV be a finite vertex set indexing random variables X=(Xv)v∈VX = (X_v)_{v \in V} taking values in a product space X\mathcal{X}. Let M∘\mathcal{M}^{\circ} denote the collection of distributions over X\mathcal{X} that are absolutely continuous with respect to a product measure.

Each DAG D\mathcal{D} defines a statistical model consisting of distributions that factorize according to its structure: Mdag(D):={P∈M∣p(x)=∏v∈Vp(xv∣xPa⁡D(v))}\mathcal{M}_{\mathrm{dag}}(\mathcal{D}) := \{P \in\mathcal{M} \mid p(x) = \prod_{v \in V} p(x_v \mid x_{\operatorname{Pa}_{\mathcal{D}}(v)})\}, where pp denotes the density of PP. A CPDAG G\mathcal{G} represents a Markov equivalence class and defines the statistical model: M(G)=⋃D∈[G]Mdag(D)\mathcal{M}(\mathcal{G}) = \bigcup_{\mathcal{D} \in[\mathcal{G}]} \mathcal{M}_{\mathrm{dag}}(\mathcal{D}), where [G][\mathcal{G}] denotes all DAGs in the equivalence class represented by the CPDAG G\mathcal{G}.

Let G\mathfrak{G} denote the collection of all CPDAGs over VV. The model map M\mathcal{M} satisfies the following properties.

Proposition 1. For any G1,G2∈G\mathcal{G}_1, \mathcal{G}_2 \in\mathfrak{G}:

  1. Model containment: M(G1)⊆M(G2)\mathcal{M}(\mathcal{G}_1) \subseteq\mathcal{M}(\mathcal{G}_2) if and only if every conditional dependence encoded by G1\mathcal{G}_1 is also encoded by G2\mathcal{G}_2.

  1. Injectivity: G1≠G2\mathcal{G}_1 \ne\mathcal{G}_2 implies M(G1)≠M(G2)\mathcal{M}(\mathcal{G}_1) \ne\mathcal{M}(\mathcal{G}_2).

(3) Extremal models: For every G∈G\mathcal{G} \in\mathbb{G}, M(Gempty)⊆M(G)⊆M(Gfull)\mathcal{M}(\mathcal{G}_{\mathrm{empty}}) \subseteq\mathcal{M}(\mathcal{G}) \subseteq\mathcal{M}(\mathcal{G}_{\mathrm{full}}), where Gempty\mathcal{G}_{\mathrm{empty}} and Gfull\mathcal{G}_{\mathrm{full}} are the empty and complete undirected CPDAGs.

Organizing CPDAGs via posets

Definition 1 (Partially ordered set). A partially ordered set (poset) is a tuple (S,⪯)(S, \preceq) consisting of a set SS and a relation ⪯\preceq that is reflexive (a⪯aa \preceq a), antisymmetric (a⪯ba \preceq b and b⪯a⇒a=bb \preceq a \Rightarrow a=b), and transitive (a⪯ba \preceq b and b⪯c⇒a⪯cb \preceq c \Rightarrow a \preceq c).

Letting G\mathbb{G} be the collection of all CPDAGs over a fixed vertex set VV, we organize this collection according to a poset, ordered based on model inclusion, following Taeb et al. [52].

Definition 2 (CPDAG poset). The CPDAG poset is L=(G,⪯)\mathcal{L} = (\mathbb{G}, \preceq), ordered according to model inclusion, i.e., the pair of CPDAGs G1,G2∈G\mathcal{G}_1,\mathcal{G}_2 \in\mathbb{G} satisfy G1⪯G2\mathcal{G}_1 \preceq\mathcal{G}_2 if and only if M(G1)⊆M(G2)\mathcal{M}(\mathcal{G}_1) \subseteq\mathcal{M}(\mathcal{G}_2).

The second and third results of Proposition 1 establish that L\mathcal{L} is a poset with least and greatest elements, given by the fully disconnected CPDAG Gempty\mathcal{G}_{\mathrm{empty}} and fully connected CPDAG Gfull\mathcal{G}_{\mathrm{full}}, respectively. By the first result, G1⪯G2\mathcal{G}_1 \preceq\mathcal{G}_2 if and only if every conditional dependence encoded by G1\mathcal{G}_1 is also encoded by G2\mathcal{G}_2.

The CPDAG poset L\mathcal{L} has a special structure known as gradedness, which we describe using the notion of neighboring graphs.

Definition 3 (Cover and neighbor). For distinct CPDAGs G1,G2∈G\mathcal{G}_1,\mathcal{G}_2 \in\mathbb{G}, we say that G2\mathcal{G}_2 covers G1\mathcal{G}_1, written G1⊲G2\mathcal{G}_1 \lhd\mathcal{G}_2, if G1⪯G2\mathcal{G}_1 \preceq\mathcal{G}_2, and no G∈G∖{G1,G2}\mathcal{G} \in\mathbb{G} \setminus\{\mathcal{G}_1,\mathcal{G}_2\} satisfies: G1⪯G⪯G2\mathcal{G}_1 \preceq\mathcal{G} \preceq\mathcal{G}_2. Two CPDAGs are neighbors if one covers the other.

Definition 4 (Graded poset). A poset is graded if it admits a rank function rank⁡:G→Z+\operatorname{rank}: \mathbb{G} \to\mathbb{Z}_{+} such that G1⊲G2\mathcal{G}_1 \lhd\mathcal{G}_2 means rank⁡(G2)=rank⁡(G1)+1\operatorname{rank}(\mathcal{G}_2) = \operatorname{rank}(\mathcal{G}_1) + 1.

The CPDAG poset L\mathcal{L} is graded with rank function rank⁡(G)=∣Skel⁡(G)∣\operatorname{rank}(\mathcal{G}) = \lvert\operatorname{Skel}(\mathcal{G}) \rvert, where Skel⁡(G)\operatorname{Skel}(\mathcal{G}) denotes the edge set of its skeleton. Thus, rank measures graphical complexity, and neighboring CPDAGs differ in rank by one.

The poset of CPDAGs can be visualized by a Hasse diagram shown in Figure 3. Each box is a CPDAG; if G2\mathcal{G}_2 covers G1\mathcal{G}_1, we then place G2\mathcal{G}_2 above G1\mathcal{G}_1 and draw an upward arrow G1→G2\mathcal{G}_1 \to\mathcal{G}_2. Partial order can be read off from the diagram: G1⪯G2\mathcal{G}_1 \preceq\mathcal{G}_2 if there exists a directed path (can be of length zero) from G1\mathcal{G}_1 to G2\mathcal{G}_2.

Figure 3. Hasse diagram of the CPDAG poset on 3 nodes. Each box represents a CPDAG, and each dashed arrow represents a covering relation, i.e., we draw G1→G2\mathcal{G}_1 \to\mathcal{G}_2 pointing upwards if G2\mathcal{G}_2 covers G1\mathcal{G}_1. We can determine whether G1⪯G2\mathcal{G}_1 \preceq\mathcal{G}_2 by checking whether there is a directed path from G1\mathcal{G}_1 to G2\mathcal{G}_2. The poset has a least and a greatest element, the empty graph and the full graph, respectively. The rank, which is the number of edges in the graph, is indicated.

Confidence region over CPDAGs

Setup

Let X=(X1,…,Xp)X = (X_1,\ldots,X_p) denote a collection of pp jointly Gaussian random variables with joint distribution P⋆P^\star. We assume that P⋆P^\star is faithful to a CPDAG G⋆G^\star over the vertex set V=[p]V = [p], where each vertex i∈Vi \in V corresponds to the random variable XiX_i. This is formalized next.

Assumption 1 (Faithfulness). For all disjoint subsets A,B,C⊂VA,B,C \subset V:

XA and XB d-separated by XC in G⋆⟺XA⊥ ⁣ ⁣ ⁣⊥XB∣XC in P⋆.X_{A} \text{ and } X_{B}\ d\text{-separated by } X_{C} \text{ in } G^{\star} \Longleftrightarrow X_{A} \perp\!\!\!\perp X_{B} \mid X_{C} \text{ in } P^{\star}.

We let G\mathcal{G} denote the collection of all CPDAGs over VV and suppose that we observe nn independent and identically distributed realizations of XX from P⋆P^\star.

A central goal in causal structure learning is to infer G⋆G^\star from observational data. While existing causal discovery methods typically produce a single estimated CPDAG, such point estimates do not directly quantify the uncertainty associated with the learned graphical structure. To address this limitation, we consider constructing data-dependent collections of CPDAGs that contain the true CPDAG with a prescribed probability, at least asymptotically. Such collections provide a principled way to represent uncertainty in the underlying causal structure.

References

  1. [1]Andersson, S. A., Madigan, D. and Perlman, M. D. (1997), ‘A characterization of Markov equivalence classes for acyclic digraphs’, The Annals of Statistics 25, 505–541.DOI
  2. [2]Bang, C. W. and Dideléz, V. (2023), ‘Do we become wiser with time? On causal equivalence with tiered background knowledge, in ‘Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence’, Vol. 216 of Proceedings of Machine Learning Research, PMLR, pp. 119–129.
  3. [3]Bartlett, M. and Cussens, J. (2017), ‘Integer linear programming for the Bayesian network structure learning problem’, Artificial Intelligence 244.
  4. [4]Chang, T.-H., Guo, Z. and Malinsky, D. (2026), ‘Post-selection inference for causal effects after causal discovery’, Biometrika 113(1), asaf073.DOI
  5. [5]Chickering, D. M. (1995), a transformational characterization of equivalent bayesian network structures, in ‘Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence’, pp. 87–98.
  6. [6]Chickering, D. M. (2002), ‘Optimal structure identification with greedy search’, Journal of Machine Learning Research 3, 507–554.
  7. [7]Chickering, D. M. and Meek, C. (2002), Finding optimal bayesian networks, in ‘Conference on Uncertainty in Artificial Intelligence’.
  8. [8]Colombo, D. and Maathuis, M. H. (2012), ‘Order-independent constraint-based causal structure learning’, Journal of Machine Learning Research 15, 3741–3782.
  9. [9]Colombo, D. and Maathuis, M. H. (2014), ‘Order-independent constraint-based causal structure learning’, Journal of Machine Learning Research 15(16), 3921–3962.
  10. [10]Cussens, J., Haws, D. and Studený, M. (2017), ‘Polyhedral aspects of score equivalence in Bayesian network structure learning’, Mathematical Programming 164.
  11. [11]Cussens, J., Järvisalo, M., Korhonen, J. H. and Bartlett, M. (2017), ‘Bayesian network structure learning with integer programming: Polytopes, facets and complexity’, Journal of Artificial Intelligence Research 58.
  12. [12]Drton, M. and Maathuis, M. H. (2017), ‘Structure learning in graphical modeling’, Annual Review of Statistics and Its Application 4(1), 365–393.arxiv.org/abs/1606.02359
  13. [13]Friedman, N., Goldszmidt, M. and Wyner, A. (1999), Data analysis with Bayesian networks: A bootstrap approach, in ‘Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI)’, pp. 196–205.
  14. [14]Friedman, N. and Koller, D. (2003), ‘Being Bayesian about network structure. A Bayesian approach to structure discovery in Bayesian networks’, Machine Learning 50(1–2), 95–125.
  15. [15]Friedman, N., Linial, M., Nachman, I. and Pe’er, D. (2000), ‘Using bayesian networks to analyze expression data’, Journal of Computational Biology 7, 601–620.
  16. [16]Glymour, C., Zhang, K. and Spirtes, P. (2019), ‘Review of causal discovery methods based on graphical models’, Frontiers in Genetics 10, 524.DOI
  17. [17]Gradu, P., Zrnic, T., Wang, Y. and Jordan, M. I. (2025), ‘Valid inference after causal discovery’, Journal of the American Statistical Association 120(550), 1127–1138.arxiv.org/abs/2208.05949
  18. [18]Greenland, S., Pearl, J. and Robins, J. M. (1999), ‘Causal diagrams for epidemiologic research.’, Epidemiology 10.pubmed.ncbi.nlm.nih.gov/9888278
  19. [19]Harris, N. and Drton, M. (2013), ‘Pc algorithm for nonparanormal graphical models’, Journal of Machine Learning Research 14, 3365–3383.DOI
  20. [20]Hart, P. E., Nilsson, N. J. and Raphael, B. (1968), ‘A formal basis for the heuristic determination of minimum cost paths’, IEEE transactions on Systems Science and Cybernetics 4(2), 100–107.
  21. [21]Hernán, M. A. and Robins, J. M. (2020), Causal Inference: What If, Chapman & Hall/CRC, Boca Raton.
  22. [22]Huang, B., Zhang, K., Lin, Y., Schölkopf, B. and Glymour, C. (2018), Generalized score functions for causal discovery, in ‘Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining’.DOI
  23. [23]Jaakkola, T., Sontag, D., Globerson, A. and Meila, M. (2010), Learning bayesian network structure using lp relaxations, in ‘Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics’.
  24. [24]Kalisch, M. and Bühlmann, P. (2007), ‘Estimating high-dimensional directed acyclic graphs with the PC-algorithm’, Journal of Machine Learning Research 8, 613–636.
  25. [25]Karp, R. M. (1972), Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher, eds, ‘Complexity of Computer Computations’, Plenum Press, New York, pp. 85–103.
  26. [26]Kendall, M. G. (1938), ‘A new measure of rank correlation’, Biometrika 30(1-2), 81–93.DOI
  27. [27]Kocka, T., Bouckaert, R. R. and Studený, M. (2001), On characterizing inclusion of bayesian networks, in ‘Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (UAI)’, pp. 261–268.
  28. [28]Küçükyavuz, S., Shojaie, A., Manzour, H., Wei, L. and Wu, H.-H. (2023), ‘Consistent second-order conic integer programming for learning Bayesian networks’, Journal of Machine Learning Research 24(322), 1–38.
  29. [29]Kuipers, J. and Moffa, G. (2017), ‘Partition MCMC for inference on acyclic digraphs’, Journal of the American Statistical Association 112(517), 282–299.
  30. [30]Lauritzen, S. L. (1996), Graphical models, Vol. 17, Clarendon Press.
  31. [31]Manzour, H., Küçükyavuz, S., Wu, H.-H. and Shojaie, A. (2021), ‘Integer programming for learning directed acyclic graphs from continuous data’, INFORMS Journal on Optimization 3(1), 46–73.DOI
  32. [32]Meek, C. (1995), ‘Causal inference and causal explanation with background knowledge’, in ‘Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence (UAI)’, pp. 403–410.
  33. [33]Meila, M. (2005), Comparing clusterings: An automatic view, in ‘Proceedings of the Twenty-Second International Conference on Machine Learning (ICML)’, pp. 577–584.
  34. [34]Micali, S. and Vazirani, V. V. (1980), An O(√|V| |E|) algorithm for finding maximum matching in general graphs, in ‘21st Annual Symposium on Foundations of Computer Science (SFCS 1980)’, IEEE, pp. 17–27.
  35. [35]Nandy, P., Hauser, A. and Maathuis, M. (2018), ‘High-dimensional consistency in score-based and hybrid structure learning’, The Annals of Statistics 46(6A), 3151–3183.
  36. [36]Niinimaki, T., Parviainen, P. and Koivisto, M. (2016), ‘Structure discovery in bayesian networks by sampling partial orders’, Journal of Machine Learning Research 17, 57:1–57:47.
  37. [37]Pearl, J. (1995), ‘Causal diagrams for empirical research’, Biometrika 82(4), 669–688.
  38. [38]Pearl, J. (2009), Causality, 2nd edn, Cambridge University Press.
  39. [39]Peters, J., Janzing, D. and Schölkopf, B. (2017), Elements of Causal Inference: Foundations and Learning Algorithms, The MIT Press.
  40. [40]Ramsey, J., Zhang, J. and Spirtes, P. L. (2006), Adjacency-faithfulness and conservative causal inference, in ‘Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence’, pp. 401–408.
  41. [41]Robins, J. M., Scheines, R., Spirtes, P. and Wasserman, L. (2003), ‘Uniform consistency in causal inference’, Biometrika 90(3), 491–515.DOI
  42. [42]Rose, D. J., Tarjan, R. E. and Lueker, G. S. (1976), ‘Algorithmic aspects of vertex elimination on graphs’, SIAM Journal on Computing 5(2), 266–283.DOI
  43. [43]Runge, J., Bathiany, S., Bollt, E., Camps-Valls, G., Coumou, D., Deyle, E., Glymour, C., Kretschmer, M., Mahecha, M. D., Muñoz-Marí, J., van Nes, E. H., Peters, J., Quax, R., Reichstein, M., Scheffer, M., Schölkopf, B., Spirtes, P., Sugihara, G., Sun, J., Zhang, K. and Zscheischler, J. (2019), ‘Inferring causation from time series in earth system sciences’, Nature Communications 10.
  44. [44]Sachs, K., Perez, O. D., Pe’er, D., Lauffenburger, D. A. and Nolan, G. P. (2005), ‘Causal protein-signaling networks derived from multiparameter single-cell data’, Science 308, 523 – 529.
  45. [45]Silander, T. and Myllymäki, P. (2006), A simple approach for finding the globally optimal Bayesian network structure, in ‘Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence’, p. 445–452.
  46. [46]Smith, S. M., Miller, K. L., Salimi-Khorshidi, G., Webster, M. A., Beckmann, C. F., Nichols, T. E., Ramsey, J. and Woolrich, M. W. (2011), ‘Network modelling methods for fmri’, NeuroImage 54.
  47. [47]Sondhi, A. and Shojaie, A. (2019), ‘The reduced PC-algorithm: Improved causal structure learning in large random networks’, Journal of Machine Learning Research 20(164), 1–31.
  48. [48]Spirtes, P., Glymour, C. and Scheines, R. (2000), Causation, Prediction, and Search, 2nd edn, MIT Press, Cambridge, MA.
  49. [49]Strieder, D. and Drton, M. (2023), ‘Confidence in causal inference under structure uncertainty in linear causal models with equal variances’, Journal of Causal Inference 11(1), 20230030.
  50. [50]Strieder, D. and Drton, M. (2024), Dual likelihood for causal inference under structure uncertainty, in ‘Proceedings of the Third Conference on Causal Learning and Reasoning (CLeaR)’, Vol. 236, pp. 1–17.
  51. [51]Strieder, D., Freidling, T., Haffner, S. and Drton, M. (2021), ‘Confidence in causal discovery with linear causal models, in ‘Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence (UAI)’, Vol. 161, pp. 1217–1226.
  52. [52]Taeb, A., Bühlmann, P. and Chandrasekaran, V. (2024), ‘Model selection over partially ordered sets’, Proceedings of the National Academy of Sciences of the United States of America 121(8), e2314228121.DOI
  53. [53]Taeb, A., Guo, F. and Henckel, L. (2026), ‘Model-oriented graph distances via partially ordered sets’, arXiv preprint arXiv:2511.10625.arxiv.org/abs/2511.10625
  54. [54]Tsamardinos, I., Brown, L. E. and Aliferis, C. F. (2006), ‘The max-min hill-climbing Bayesian network structure learning algorithm’, Machine Learning 65(1), 31–78.DOI
  55. [55]Uhler, C., Raskutti, G., Bühlmann, P. and Yu, B. (2013), ‘Geometry of the faithfulness assumption in causal inference’, The Annals of Statistics 41(2), 436–463.DOI
  56. [56]Verma, T. and Pearl, J. (1990), ‘Equivalence and synthesis of causal models’, in ‘Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence (UAI)’, pp. 255–270.
  57. [57]Wang, Y. S., Kolar, M. and Drton, M. (2026), ‘Confidence sets for causal orderings’, Journal of the American Statistical Association 121(553), 690–703.arxiv.org/abs/2305.14506
  58. [58]Wilson, D. B. (1996), ‘Generating random spanning trees more quickly than the cover time’, in ‘Symposium on the Theory of Computing’.DOI
  59. [60]Yannakakis, M. (1981), ‘Computing the minimum fill-in is NP-complete’, SIAM Journal on Algebraic and Discrete Methods 2(1), 77–79.DOI
  60. [62]Yuan, C. and Malone, B. M. (2013), ‘Learning optimal bayesian networks: A shortest path perspective’, Journal of Artificial Intelligence Research 48, 23–65.DOI
  61. [63]Zhang, J. and Spirtes, P. (2003), Strong faithfulness and uniform consistency in causal inference, in ‘Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence’, pp. 632–639.
  62. [64]Zhang, X., Keret, N., Shojaie, A. and Taeb, A. (2025), ‘Convex mixed-integer programming for causal additive models with optimization and statistical guarantees’, arxiv preprint arXiv:2511.21126.arxiv.org/abs/2511.21126
  63. [65]Zheng, X., Aragam, B., Ravikumar, P. K. and Xing, E. P. (2018), ‘DAGs with NO TEARS: continuous optimization for structure learning’, Advances in Neural Information Processing Systems 31, 9492–9503.arxiv.org/abs/1803.01422

Paper details

vlnc:W_45fvmmr7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents