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 log n / M , where n n n is the sample size and M M M is the number of perturbed runs, so it decreases as M M M 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} 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 = 10 p = 10 p = 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 n n n using perturbed PC with M = 1000 M = 1000 M = 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.
Figure 1. Empirical confidence ball coverage (left) and mean ball radius (right) for a synthetic setting with p = 10 p = 10 p = 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) G = ( V , E ) consists of a finite set of vertices V V V and a set of edges E E E . We consider two types of edges: directed ( u → v ) (u \to v) ( u → v ) and undirected ( u − v ) (u - v) ( u − v ) . The skeleton of G \mathcal{G} G , denoted Skel ( G ) \operatorname{Skel}(\mathcal{G}) Skel ( G ) , is the undirected graph obtained by replacing all directed edges in G \mathcal{G} G with undirected edges. A graph G ′ = ( V , E ′ ) \mathcal{G}' = (V, E') G ′ = ( V , E ′ ) is a subgraph of G = ( V , E ) \mathcal{G} = (V, E) G = ( V , E ) if E ′ ⊆ E E' \subseteq E E ′ ⊆ E . A cycle is a sequence of distinct vertices v 1 , … , v k v_1, \ldots, v_k v 1 , … , v k (k ≥ 3 k \ge3 k ≥ 3 ) such that there is an edge between every two adjacent vertices in the sequence and between v k v_k v k and v 1 v_1 v 1 . A directed cycle is a cycle where all edges are directed v 1 → v 2 → ⋯ → v k → v 1 v_1 \to v_2 \to\cdots\to v_k \to v_1 v 1 → v 2 → ⋯ → v k → 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} D , let Pa D ( v ) \operatorname{Pa}_{\mathcal{D}}(v) Pa D ( v ) denote the set of parents of vertex v v v , i.e., { u ∈ V ∣ u → v ∈ E } \{u \in V \mid u \to v \in E\} { u ∈ V ∣ u → v ∈ E } . A triple of vertices ( u , v , w ) (u, v, w) ( u , v , w ) forms a v v v -structure (or unshielded collider) if u → v ← w u \to v \leftarrow w u → v ← w exists in the graph and there is no edge between u u u and w w w . 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} G , denoted Skel ( G ) \operatorname{Skel}(\mathcal{G}) Skel ( G ) , is the undirected graph obtained by replacing all directed edges with undirected edges.
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 V V V be a finite vertex set indexing random variables X = ( X v ) v ∈ V X = (X_v)_{v \in V} X = ( X v ) v ∈ V taking values in a product space X \mathcal{X} X . Let M ∘ \mathcal{M}^{\circ} M ∘ denote the collection of distributions over X \mathcal{X} X that are absolutely continuous with respect to a product measure.
Each DAG D \mathcal{D} D defines a statistical model consisting of distributions that factorize according to its structure: M d a g ( D ) : = { P ∈ M ∣ p ( x ) = ∏ v ∈ V p ( x v ∣ x Pa 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)})\} M dag ( D ) := { P ∈ M ∣ p ( x ) = ∏ v ∈ V p ( x v ∣ x Pa D ( v ) )} , where p p p denotes the density of P P P . A CPDAG G \mathcal{G} G represents a Markov equivalence class and defines the statistical model: M ( G ) = ⋃ D ∈ [ G ] M d a g ( D ) \mathcal{M}(\mathcal{G}) = \bigcup_{\mathcal{D} \in[\mathcal{G}]} \mathcal{M}_{\mathrm{dag}}(\mathcal{D}) M ( G ) = ⋃ D ∈ [ G ] M dag ( D ) , where [ G ] [\mathcal{G}] [ G ] denotes all DAGs in the equivalence class represented by the CPDAG G \mathcal{G} G .
Let G \mathfrak{G} G denote the collection of all CPDAGs over V V V . The model map M \mathcal{M} M satisfies the following properties.
Proposition 1. For any G 1 , G 2 ∈ G \mathcal{G}_1, \mathcal{G}_2 \in\mathfrak{G} G 1 , G 2 ∈ G :
Model containment: M ( G 1 ) ⊆ M ( G 2 ) \mathcal{M}(\mathcal{G}_1) \subseteq\mathcal{M}(\mathcal{G}_2) M ( G 1 ) ⊆ M ( G 2 ) if and only if every conditional dependence encoded by G 1 \mathcal{G}_1 G 1 is also encoded by G 2 \mathcal{G}_2 G 2 .
Injectivity: G 1 ≠ G 2 \mathcal{G}_1 \ne\mathcal{G}_2 G 1 = G 2 implies M ( G 1 ) ≠ M ( G 2 ) \mathcal{M}(\mathcal{G}_1) \ne\mathcal{M}(\mathcal{G}_2) M ( G 1 ) = M ( G 2 ) .
(3) Extremal models: For every G ∈ G \mathcal{G} \in\mathbb{G} G ∈ G , M ( G e m p t y ) ⊆ M ( G ) ⊆ M ( G f u l l ) \mathcal{M}(\mathcal{G}_{\mathrm{empty}}) \subseteq\mathcal{M}(\mathcal{G}) \subseteq\mathcal{M}(\mathcal{G}_{\mathrm{full}}) M ( G empty ) ⊆ M ( G ) ⊆ M ( G full ) , where G e m p t y \mathcal{G}_{\mathrm{empty}} G empty and G f u l l \mathcal{G}_{\mathrm{full}} G 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) ( S , ⪯ ) consisting of a set S S S and a relation ⪯ \preceq ⪯ that is reflexive (a ⪯ a a \preceq a a ⪯ a ), antisymmetric (a ⪯ b a \preceq b a ⪯ b and b ⪯ a ⇒ a = b b \preceq a \Rightarrow a=b b ⪯ a ⇒ a = b ), and transitive (a ⪯ b a \preceq b a ⪯ b and b ⪯ c ⇒ a ⪯ c b \preceq c \Rightarrow a \preceq c b ⪯ c ⇒ a ⪯ c ).
Letting G \mathbb{G} G be the collection of all CPDAGs over a fixed vertex set V V V , 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) L = ( G , ⪯ ) , ordered according to model inclusion, i.e., the pair of CPDAGs G 1 , G 2 ∈ G \mathcal{G}_1,\mathcal{G}_2 \in\mathbb{G} G 1 , G 2 ∈ G satisfy G 1 ⪯ G 2 \mathcal{G}_1 \preceq\mathcal{G}_2 G 1 ⪯ G 2 if and only if M ( G 1 ) ⊆ M ( G 2 ) \mathcal{M}(\mathcal{G}_1) \subseteq\mathcal{M}(\mathcal{G}_2) M ( G 1 ) ⊆ M ( G 2 ) .
The second and third results of Proposition 1 establish that L \mathcal{L} L is a poset with least and greatest elements, given by the fully disconnected CPDAG G e m p t y \mathcal{G}_{\mathrm{empty}} G empty and fully connected CPDAG G f u l l \mathcal{G}_{\mathrm{full}} G full , respectively. By the first result, G 1 ⪯ G 2 \mathcal{G}_1 \preceq\mathcal{G}_2 G 1 ⪯ G 2 if and only if every conditional dependence encoded by G 1 \mathcal{G}_1 G 1 is also encoded by G 2 \mathcal{G}_2 G 2 .
The CPDAG poset L \mathcal{L} 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 G 1 , G 2 ∈ G \mathcal{G}_1,\mathcal{G}_2 \in\mathbb{G} G 1 , G 2 ∈ G , we say that G 2 \mathcal{G}_2 G 2 covers G 1 \mathcal{G}_1 G 1 , written G 1 ⊲ G 2 \mathcal{G}_1 \lhd\mathcal{G}_2 G 1 ⊲ G 2 , if G 1 ⪯ G 2 \mathcal{G}_1 \preceq\mathcal{G}_2 G 1 ⪯ G 2 , and no G ∈ G ∖ { G 1 , G 2 } \mathcal{G} \in\mathbb{G} \setminus\{\mathcal{G}_1,\mathcal{G}_2\} G ∈ G ∖ { G 1 , G 2 } satisfies: G 1 ⪯ G ⪯ G 2 \mathcal{G}_1 \preceq\mathcal{G} \preceq\mathcal{G}_2 G 1 ⪯ G ⪯ 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}_{+} rank : G → Z + such that G 1 ⊲ G 2 \mathcal{G}_1 \lhd\mathcal{G}_2 G 1 ⊲ G 2 means rank ( G 2 ) = rank ( G 1 ) + 1 \operatorname{rank}(\mathcal{G}_2) = \operatorname{rank}(\mathcal{G}_1) + 1 rank ( G 2 ) = rank ( G 1 ) + 1 .
The CPDAG poset L \mathcal{L} L is graded with rank function rank ( G ) = ∣ Skel ( G ) ∣ \operatorname{rank}(\mathcal{G}) = \lvert\operatorname{Skel}(\mathcal{G}) \rvert rank ( G ) = ∣ Skel ( G )∣ , where Skel ( G ) \operatorname{Skel}(\mathcal{G}) Skel ( 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 G 2 \mathcal{G}_2 G 2 covers G 1 \mathcal{G}_1 G 1 , we then place G 2 \mathcal{G}_2 G 2 above G 1 \mathcal{G}_1 G 1 and draw an upward arrow G 1 → G 2 \mathcal{G}_1 \to\mathcal{G}_2 G 1 → G 2 . Partial order can be read off from the diagram: G 1 ⪯ G 2 \mathcal{G}_1 \preceq\mathcal{G}_2 G 1 ⪯ G 2 if there exists a directed path (can be of length zero) from G 1 \mathcal{G}_1 G 1 to G 2 \mathcal{G}_2 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 G 1 → G 2 \mathcal{G}_1 \to\mathcal{G}_2 G 1 → G 2 pointing upwards if G 2 \mathcal{G}_2 G 2 covers G 1 \mathcal{G}_1 G 1 . We can determine whether G 1 ⪯ G 2 \mathcal{G}_1 \preceq\mathcal{G}_2 G 1 ⪯ G 2 by checking whether there is a directed path from G 1 \mathcal{G}_1 G 1 to G 2 \mathcal{G}_2 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 = ( X 1 , … , X p ) X = (X_1,\ldots,X_p) X = ( X 1 , … , X p ) denote a collection of p p p jointly Gaussian random variables with joint distribution P ⋆ P^\star P ⋆ . We assume that P ⋆ P^\star P ⋆ is faithful to a CPDAG G ⋆ G^\star G ⋆ over the vertex set V = [ p ] V = [p] V = [ p ] , where each vertex i ∈ V i \in V i ∈ V corresponds to the random variable X i X_i X i . This is formalized next.
Assumption 1 (Faithfulness). For all disjoint subsets A , B , C ⊂ V A,B,C \subset V A , B , C ⊂ V :
X A and X B d -separated by X C in G ⋆ ⟺ X A ⊥ ⊥ X B ∣ X C 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}. X A and X B d -separated by X C in G ⋆ ⟺ X A ⊥ ⊥ X B ∣ X C in P ⋆ .
We let G \mathcal{G} G denote the collection of all CPDAGs over V V V and suppose that we observe n n n independent and identically distributed realizations of X X X from P ⋆ P^\star P ⋆ .
A central goal in causal structure learning is to infer G ⋆ G^\star G ⋆ 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.
Definition 5 (Asymptotically valid confidence region). A collection of CPDAGs G ^ n \widehat{\mathcal{G}}_n G n learned from data of size n n n is said to be an asymptotically valid 1 − α 1-\alpha 1 − α confidence region for G ⋆ G^\star G ⋆ if lim inf n → ∞ P ( G ⋆ ∈ G ^ n ) ≥ 1 − α \liminf_{n\to\infty}\mathbb{P}(G^\star\in\widehat{\mathcal{G}}_n) \ge1-\alpha lim inf n → ∞ P ( G ⋆ ∈ G n ) ≥ 1 − α .
Two types of confidence regions
In this paper, we consider two types of confidence regions, based on balls and intervals, both constructed using the poset structure of CPDAGs.
The first approach constructs a confidence ball around a data-dependent center, typically a point estimate of the true CPDAG. The ball contains all CPDAGs within a specified distance of this center, where the distance quantifies structural differences between graphical models using the underlying poset. The radius determines the size of the region and is chosen to achieve the desired coverage probability. Formally, we define a confidence ball as follows.
Definition 6 (Ball). A region G ^ n b a l l ⊆ G \widehat{\mathcal{G}}_n^{\mathrm{ball}} \subseteq\mathcal{G} G n ball ⊆ G is called a ball if
G ^ n b a l l = { G ∈ G , d ( G , G ^ 0 , n ) ≤ r ^ n } , (1) \widehat{\mathcal{G}}_n^{\mathrm{ball}} = \{G \in\mathcal{G}, d(G,\widehat{G}_{0,n}) \leq\widehat{r}_n\}, \tag*{(1)} G n ball = { G ∈ G , d ( G , G 0 , n ) ≤ r n } , (1) where G ^ 0 , n ∈ G \widehat{G}_{0,n} \in\mathcal{G} G 0 , n ∈ G and r ^ n ∈ Z ≥ 0 \widehat{r}_n \in\mathbb{Z}_{\geq0} r n ∈ Z ≥ 0 are a data-dependent center and radius, respectively, and d ( ⋅ , ⋅ ) d(\cdot,\cdot) d ( ⋅ , ⋅ ) is a metric over the space of CPDAGs.
In Section 3.3, we describe a distance metric tailored to the CPDAG poset. A valid confidence region can always be defined by setting r ^ n = max G 1 , G 2 ∈ G d ( G 1 , G 2 ) \widehat{r}_n = \max_{G_1,G_2 \in\mathcal{G}} d(G_1,G_2) r n = max G 1 , G 2 ∈ G d ( G 1 , G 2 ) , which yields G ^ n = G \widehat{\mathcal{G}}_n = \mathcal{G} G n = G . This construction, however, simply returns the full collection and is therefore uninformative. Our goal is to construct smaller confidence balls that retain the desired coverage guarantee.
The second approach constructs a region using the partial ordering of CPDAGs. Rather than considering graphs within a specified distance of a center, this approach identifies data-dependent lower and upper bounds, and includes all CPDAGs lying between them in the poset. We formalize this notion below.
Definition 7 (Interval). A region G ^ n i n t e r v a l ⊆ G \widehat{\mathcal{G}}_n^{\mathrm{interval}} \subseteq\mathcal{G} G n interval ⊆ G is called an interval if:
G ^ n i n t e r v a l = { G ∈ G , G ^ n , L ⪯ G ⪯ G ^ n , U } , \widehat{\mathcal{G}}_n^{\mathrm{interval}} = \{G \in\mathcal{G}, \widehat{G}_{n,L} \preceq G \preceq\widehat{G}_{n,U}\}, G n interval = { G ∈ G , G n , L ⪯ G ⪯ G n , U } , where G ^ n , L , G ^ n , U ∈ G \widehat{G}_{n,L},\widehat{G}_{n,U} \in\mathcal{G} G n , L , G n , U ∈ G are data-dependent lower and upper bounds satisfying G ^ n , L ⪯ G ^ n , U \widehat{G}_{n,L} \preceq\widehat{G}_{n,U} G n , L ⪯ G n , U , and ⪯ \preceq ⪯ denotes the partial order on CPDAGs.
Choosing the least and greatest elements of the poset as bounds yields the trivial region G ^ n i n t e r v a l = G \widehat{\mathcal{G}}_n^{\mathrm{interval}} = \mathcal{G} G n interval = G , which has coverage probability one. Our goal is instead to construct tighter intervals that retain the desired coverage guarantee, with width measured by
width ( G ^ n i n t e r v a l ) = rank ( G ^ n , U ) − rank ( G ^ n , L ) ∈ [ 0 , p ( p − 1 ) / 2 ] \operatorname{width}(\widehat{\mathcal{G}}_n^{\mathrm{interval}}) = \operatorname{rank}(\widehat{G}_{n,U}) - \operatorname{rank}(\widehat{G}_{n,L}) \in[0,p(p-1)/2] width ( G n interval ) = rank ( G n , U ) − rank ( G n , L ) ∈ [ 0 , p ( p − 1 ) /2 ]
The region G ^ n i n t e r v a l \widehat{\mathcal{G}}_n^{\mathrm{interval}} G n interval has a natural interpretation. If it is a valid confidence region, then, with high probability, the conditional dependencies encoded by the true graph contain those encoded by G ^ n , L \widehat{G}_{n,L} G n , L and are contained in those encoded by G ^ n , U \widehat{\mathcal{G}}_{n,U} G n , U . In particular, with high probability, every edge of G ^ n , L \widehat{\mathcal{G}}_{n,L} G n , L and every v-structure shared by G ^ n , L \widehat{\mathcal{G}}_{n,L} G n , L and G ^ n , U \widehat{\mathcal{G}}_{n,U} G n , U must also be present in the true graph.
Model-oriented distance between CPDAGs
For the distance metric in the definition of ball region in Definition 6, we use the model-oriented distance, first proposed in Taeb et al. [53 ] and defined next.
Definition 8 (Model-oriented distance). Let L : = ( G , ⪯ ) \mathcal{L}:=(\mathcal{G},\preceq) L := ( G , ⪯ ) be the CPDAG poset. Then, for G s , G t ∈ G \mathcal{G}_s,\mathcal{G}_t\in\mathcal{G} G s , G t ∈ G , the model-oriented distance between ( G s , G t ) (\mathcal{G}_s,\mathcal{G}_t) ( G s , G t ) is:
d m o d e l ( G s , G t ) : = min { length ( p ) : p is a path between G s and G t in the Hasse diagram of L } , (2) d_{\mathrm{model}}(\mathcal{G}_s,\mathcal{G}_t):=\min\{\operatorname{length}(p):p\text{ is a path between }\mathcal{G}_s\text{ and }\mathcal{G}_t\text{ in the Hasse diagram of }\mathcal{L}\}, \tag*{(2)} d model ( G s , G t ) := min { length ( p ) : p is a path between G s and G t in the Hasse diagram of L } , (2) where the path can contain dashed arrows in both directions. In other words, a path is a sequence ( G 0 : = G s , G 1 , G 2 , … , G k : = G t ) (\mathcal{G}_0:=\mathcal{G}_s,\mathcal{G}_1,\mathcal{G}_2,\ldots,\mathcal{G}_k:=\mathcal{G}_t) ( G 0 := G s , G 1 , G 2 , … , G k := G t ) such that G i + 1 \mathcal{G}_{i+1} G i + 1 and G i \mathcal{G}_i G i are neighbors (i.e., G i + 1 ≺ G i \mathcal{G}_{i+1}\prec\mathcal{G}_i G i + 1 ≺ G i or G i ≺ G i + 1 \mathcal{G}_i\prec\mathcal{G}_{i+1} G i ≺ G i + 1 ); see Definition 3.
As d m o d e l d_{\mathrm{model}} d model is a shortest path distance, it is a metric. Since the poset is organized by model inclusion, the model-oriented distance d m o d e l ( G s , G t ) d_{\mathrm{model}}(\mathcal{G}_s,\mathcal{G}_t) d model ( G s , G t ) measures the minimum number of basic operations needed to transform the model of G s \mathcal{G}_s G s into that of G t \mathcal{G}_t G t . Figure 4 provides an illustration. We note that defining distance through the minimal number of basic operations to transform one model to the other is common in other combinatorial settings such as ranking Kendall [26 ] and clustering Meila [33 ] .
Figure 4. A path in the poset between two CPDAGs G s \mathcal{G}_s G s and G t \mathcal{G}_t G t , shown in black. The path has length two, and no shorter path exists. Thus, d m o d e l ( G s , G t ) = 2 d_{\mathrm{model}}(\mathcal{G}_s,\mathcal{G}_t)=2 d model ( G s , G t ) = 2 .
The most popular approach for measuring distance between CPDAGs is the structural Hamming distance (SHD) Tsamardinos et al. [54 ] , which counts the number of edges that differ between the two graphs. However, as highlighted in Taeb et al. [53 ] , this distance is model-agnostic – it disregards the specific models the graphs represent and is solely defined on the graphs themselves. SHD treats each edge individually, ignoring that not all edge configurations may give a valid CPDAG. The model-agnostic nature of SHD leads to many undesirable behaviors: as outlined in the following example, a pair of CPDAGs that are very close in terms of the models they represent can have a large SHD distance.
Example 1. Let G 1 \mathcal{G}_1 G 1 be a fully connected CPDAG on p p p nodes. Let G 2 \mathcal{G}_2 G 2 have no edge between 1 and 2, with 1 → j ← 2 1\to j\leftarrow2 1 → j ← 2 , j = 3 , 4 , … , p j=3,4,\ldots,p j = 3 , 4 , … , p , and all pairs among 3 , … , p 3,\ldots,p 3 , … , p connected by undirected edges. Let G 3 \mathcal{G}_3 G 3 be the complete undirected CPDAG on 2 , … , p 2,\ldots,p 2 , … , p with 1 isolated. These can be seen in Figure 5 . From this we can say, G 3 ⪯ G 2 ⪯ G 1 \mathcal{G}_3\preceq\mathcal{G}_2\preceq\mathcal{G}_1 G 3 ⪯ G 2 ⪯ G 1 , d m o d e l ( G 1 , G 2 ) = 1 d_{\mathrm{model}}(\mathcal{G}_1,\mathcal{G}_2)=1 d model ( G 1 , G 2 ) = 1 and d S H D ( G 1 , G 2 ) = 2 p − 3 d_{\mathrm{SHD}}(\mathcal{G}_1,\mathcal{G}_2)=2p-3 d SHD ( G 1 , G 2 ) = 2 p − 3 , whereas d m o d e l ( G 1 , G 3 ) = d S H D ( G 1 , G 3 ) = p − 1 d_{\mathrm{model}}(\mathcal{G}_1,\mathcal{G}_3)=d_{\mathrm{SHD}}(\mathcal{G}_1,\mathcal{G}_3)=p-1 d model ( G 1 , G 3 ) = d SHD ( G 1 , G 3 ) = p − 1 . Since SHD ignores the models that the graphs represent, it regards G 3 \mathcal{G}_3 G 3 as closer to G 1 \mathcal{G}_1 G 1 than G 2 \mathcal{G}_2 G 2 , even though G 2 \mathcal{G}_2 G 2 differs from G 1 \mathcal{G}_1 G 1 by only one model change.
Figure 5. Three CPDAGs associated with Example 1 with p = 5 p = 5 p = 5 .
The discrepancy is especially important when constructing confidence balls. Under the model-oriented distance, increasing the radius by one corresponds to allowing one additional minimal model change from the center. SHD does not have this interpretation: a single model change can induce many compelled orientations and therefore a large jump in distance. Consequently, for any p − 1 ≤ r < 2 p − 3 p-1\leq r<2p-3 p − 1 ≤ r < 2 p − 3 , the SHD ball centered at G 1 \mathcal{G}_1 G 1 contains G 3 \mathcal{G}_3 G 3 , which is p − 1 p-1 p − 1 model changes away, but excludes the immediate neighboring model G 2 \mathcal{G}_2 G 2 . Thus, SHD balls can be poorly aligned with the underlying model geometry, including models that are many model changes from the center while excluding models that differ by only one.
A second related issue is that SHD balls can also have gaps between successive distance levels. For the three-node collider 1 → 2 ← 3 1 \to2 \leftarrow3 1 → 2 ← 3 , there is no distinct CPDAG at SHD 1, while valid CPDAGs exist at SHD 2. Hence, the balls of radii 0 and 1 are identical. Thus, increasing the SHD radius by one need not correspond to adding a new layer of models.
Constructing a confidence region via the perturbed PC algorithm
In this section, we propose strategies for building confidence regions using the perturbed PC algorithm. The perturbed PC algorithm (Chang et al., [4 ] ) replaces a single run of PC with a collection of runs based on perturbed conditional independence statistics, capturing sensitivity to borderline decisions and increasing the chance that one run recovers the true CPDAG. We study a generalized perturbed PC procedure in which the threshold, perturbation scale, and number of runs may vary, with the choices of Chang et al. [4 ] as a special case, and characterize how these choices affect coverage. Our default threshold grows with the number of runs to control increasingly extreme perturbations under the null, thereby suppressing spurious edge decisions across the collection. At the same time, it remains small enough for weak nonzero signals to cross the threshold in at least one run. This choice accommodates arbitrarily weak signals without imposing a strong faithfulness condition while producing tighter collections than the tuning of Chang et al. [4 ] .
Section 4.1 reviews PC and perturbed PC. Section 4.2 analyzes coverage and gives tuning parameters that guarantee it. Section 4.3 constructs confidence balls and intervals from the perturbed PC outputs.
Preliminaries: The PC algorithm and its perturbed version
We describe both the PC algorithm (Spirtes et al., [48 ] ) and its perturbed version introduced in Chang et al. [4 ] . Throughout, we have that X X X follows a jointly Gaussian distribution satisfying Assumption 1, and that we observe n n n iid samples from this distribution. The data is denoted by D \mathcal{D} D .
Standard PC algorithm. The PC algorithm starts from a complete undirected graph and removes edges through a sequence of conditional independence tests. A full description, including extensions with tiered background knowledge, is given in Appendix § 11 . In principle, any valid conditional independence test may be used, although we focus here on building test statistics from partial correlation coefficients.
For a multivariate Gaussian X X X , conditional independence is equivalent to zero partial correlation. For distinct i , j ∈ V i,j \in V i , j ∈ V and S ⊆ V ∖ { i , j } S \subseteq V \setminus\{i,j\} S ⊆ V ∖ { i , j } , let ρ i j ∣ S \rho_{ij\mid S} ρ ij ∣ S be the partial correlation of X i X_i X i and X j X_j X j given X S X_S X S , and ρ ^ i j ∣ S \hat{\rho}_{ij\mid S} ρ ^ ij ∣ S its sample analogue. Then, X i ⊥ ⊥ X j ∣ X S X_i \perp\!\!\!\perp X_j\mid X_S X i ⊥ ⊥ X j ∣ X S if and only if ρ i j ∣ S = 0 \rho_{ij\mid S}=0 ρ ij ∣ S = 0 . The PC algorithm tests this hypothesis using the Fisher statistic T ^ i j ∣ S = ∣ ψ ^ i j ∣ S ∣ / σ i j ∣ S \hat{T}_{ij\mid S} = \lvert\hat{\psi}_{ij\mid S}\rvert/\sigma_{ij\mid S} T ^ ij ∣ S = ∣ ψ ^ ij ∣ S ∣ / σ ij ∣ S where
ψ i j ∣ S : = 1 2 log 1 + ρ i j ∣ S 1 − ρ i j ∣ S , ψ ^ i j ∣ S : = 1 2 log 1 + ρ ^ i j ∣ S 1 − ρ ^ i j ∣ S , σ i j ∣ S : = ( n − ∣ S ∣ − 3 ) − 1 / 2 . \psi_{ij\mid S} := \frac{1}{2}\log\frac{1+\rho_{ij\mid S}}{1-\rho_{ij\mid S}}, \qquad\hat{\psi}_{ij\mid S} := \frac{1}{2}\log\frac{1+\hat{\rho}_{ij\mid S}}{1-\hat{\rho}_{ij\mid S}}, \qquad\sigma_{ij\mid S} := (n-\lvert S\rvert-3)^{-1/2}. ψ ij ∣ S := 2 1 log 1 − ρ ij ∣ S 1 + ρ ij ∣ S , ψ ^ ij ∣ S := 2 1 log 1 − ρ ^ ij ∣ S 1 + ρ ^ ij ∣ S , σ ij ∣ S := ( n − ∣ S ∣ − 3 ) − 1/2 .
The null is rejected when T ^ i j ∣ S \hat{T}_{ij\mid S} T ^ ij ∣ S exceeds a chosen threshold t t t . Let T \mathcal{T} T be the set of triples ( i , j , S ) (i,j,S) ( i , j , S ) with distinct i , j ∈ V i,j\in V i , j ∈ V , S ⊆ V ∖ { i , j } S\subseteq V\setminus\{i,j\} S ⊆ V ∖ { i , j } , and let L : = ∣ T ∣ L:=\lvert\mathcal{T}\rvert L := ∣ T ∣ . Indexing T \mathcal{T} T by l l l , write:
T ^ l : = ∣ ψ l σ l + U ^ l ∣ , κ l : = ∣ ψ l ∣ σ l , U ^ l : = ψ ^ l − ψ l σ l . \hat{T}_l := \left\lvert\frac{\psi_l}{\sigma_l}+\hat{U}_l\right\rvert,\qquad\kappa_l := \frac{\lvert\psi_l\rvert}{\sigma_l},\qquad\hat{U}_l := \frac{\hat{\psi}_l-\psi_l}{\sigma_l}. T ^ l := σ l ψ l + U ^ l , κ l := σ l ∣ ψ l ∣ , U ^ l := σ l ψ ^ l − ψ l .
where κ l \kappa_l κ l is the signal strength and U ^ l \hat{U}_l U ^ l is a standardized sampling error. Let T n u l l : = { l ∈ T : ψ l = 0 } \mathcal{T}_{\mathrm{null}}:=\{l\in\mathcal{T}:\psi_l=0\} T null := { l ∈ T : ψ l = 0 } , T n o n - n u l l : = T ∖ T n u l l \mathcal{T}_{\mathrm{non\text{-}null}}:=\mathcal{T}\setminus\mathcal{T}_{\mathrm{null}} T non - null := T ∖ T null , L 0 : = ∣ T n u l l ∣ L_0:=\lvert\mathcal{T}_{\mathrm{null}}\rvert L 0 := ∣ T null ∣ , L 1 : = ∣ T n o n - n u l l ∣ L_1:=\lvert\mathcal{T}_{\mathrm{non\text{-}null}}\rvert L 1 := ∣ T non - null ∣ , and define the minimum signal strength and minimum nonzero partial correlation:
κ min , n : = min l ∈ T n o n - n u l l κ l , ρ min , n : = min l ∈ T n o n - n u l l ∣ ρ l ∣ . \kappa_{\min,n} := \min_{l\in\mathcal{T}_{\mathrm{non\text{-}null}}}\kappa_l,\qquad\rho_{\min,n} := \min_{l\in\mathcal{T}_{\mathrm{non\text{-}null}}}\lvert\rho_l\rvert. κ m i n , n := l ∈ T non - null min κ l , ρ m i n , n := l ∈ T non - null min ∣ ρ l ∣ .
Since 1 2 ∣ log { ( 1 + x ) / ( 1 − x ) } ∣ ≥ ∣ x ∣ \frac{1}{2}\lvert\log\{(1+x)/(1-x)\}\rvert\geq\lvert x\rvert 2 1 ∣ log {( 1 + x ) / ( 1 − x )}∣ ≥ ∣ x ∣ , we have κ min , n ≥ ( n − k − 3 ) 1 / 2 ρ min , n \kappa_{\min,n}\geq(n-k-3)^{1/2}\rho_{\min,n} κ m i n , n ≥ ( n − k − 3 ) 1/2 ρ m i n , n , where k : = p − 2 k:=p-2 k := p − 2 is the largest conditioning-set size. Let z a : = Φ − 1 ( 1 − a ) z_a:=\Phi^{-1}(1-a) z a := Φ − 1 ( 1 − a ) where Φ \Phi Φ is the standard normal CDF. For each fixed triple l l l , under multivariate Gaussian sampling, and provided the corresponding population partial correlation stays bounded away from ± 1 \pm1 ± 1 , U ^ l ⟶ d N ( 0 , 1 ) \hat{U}_l\overset{d}{\longrightarrow}\mathcal{N}(0,1) U ^ l ⟶ d N ( 0 , 1 ) . Thus, lim sup n P ( ∣ U ^ l ∣ ≥ z a / 2 ) ≤ a \limsup_n\mathbb{P}(\lvert\hat{U}_l\rvert\geq z_a/2)\leq a lim sup n P (∣ U ^ l ∣ ≥ z a /2 ) ≤ a . Define
E n : = { max l ∈ T ∣ U ^ l ∣ ≤ z ν / 2 L } . E_n := \left\{\max_{l\in\mathcal{T}}\lvert\hat{U}_l\rvert\leq z_{\nu/2L}\right\}. E n := { l ∈ T max ∣ U ^ l ∣ ≤ z ν /2 L } .
It is straightforward to see that by a union bound, lim inf n P ( E n ) ≥ 1 − ν \liminf_n\mathbb{P}(E_n)\geq1-\nu lim inf n P ( E n ) ≥ 1 − ν .
Perturbed PC algorithm. Standard PC makes a single sequence of conditional independence decisions by comparing noisy test statistics to a fixed threshold. When population signals lie near this threshold, small sampling fluctuations can reverse individual decisions, and these errors may propagate through subsequent edge deletions and orientation steps, producing a CPDAG far from the truth. A single run therefore can easily be inaccurate and gives no indication of the sensitivity of the estimated graph to such borderline decisions.
This motivates replacing a single run of PC with a collection of nearby runs. The perturbed PC algorithm of Chang et al. [4 ] repeatedly perturbs the estimated CI statistics and reruns PC. The resulting collection of CPDAGs captures sensitivity to borderline decisions while increasing the chance that at least one run recovers the true CPDAG.
We describe a generalized version of the procedure in Chang et al. [4 ] . In run m ∈ [ M ] m\in[M] m ∈ [ M ] , for each l ∈ T l\in\mathcal{T} l ∈ T , replace ψ ^ l \hat{\psi}_l ψ ^ l by an independent draw
ψ ^ l [ m ] ∼ N ( ψ ^ l , η 2 σ l 2 ) . \hat{\psi}^{[m]}_l\sim\mathcal{N}(\hat{\psi}_l,\eta^2\sigma_l^2). ψ ^ l [ m ] ∼ N ( ψ ^ l , η 2 σ l 2 ) .
where η > 0 \eta>0 η > 0 controls the perturbation scale. Given a threshold t > 0 t>0 t > 0 , the corresponding null hypothesis is rejected when
T ^ l [ m ] > t where T ^ l [ m ] : = ∣ ψ ^ l [ m ] ∣ / σ l . \hat{T}^{[m]}_l>t\qquad\text{where}\qquad\hat{T}^{[m]}_l:=\lvert\hat{\psi}^{[m]}_l\rvert/\sigma_l. T ^ l [ m ] > t where T ^ l [ m ] := ∣ ψ ^ l [ m ] ∣ / σ l .
Because sampling errors can lead to incompatible edge orientations, not every run produces a valid CPDAG. We only retain runs that return a valid CPDAG. These valid runs are indexed by the elements of K ^ n \widehat{\mathcal{K}}_n K n and define
G ^ n : = { G ^ n [ m ] : m ∈ K ^ n } . \widehat{\mathcal{G}}_n:=\{\widehat{\mathcal{G}}^{[m]}_n:m\in\widehat{\mathcal{K}}_n\}. G n := { G n [ m ] : m ∈ K n } .
The full procedure is given in Algorithm 1. The implementation of Chang et al. [4 ] corresponds to η = 1 \eta=1 η = 1 , and t = c ⋆ ( log n / M ) 1 / L z ν / 2 L t=c^\star(\log n/M)^{1/L}z_{\nu/2L} t = c ⋆ ( log n / M ) 1/ L z ν /2 L for some constant c ⋆ > 0 c^\star>0 c ⋆ > 0 .
Algorithm 1: Perturbed PC algorithm
Input: Data D \mathcal{D} D , threshold t > 0 t > 0 t > 0 , perturbation scale η > 0 \eta> 0 η > 0 , number of runs M M M . Default choice η = 1 \eta= 1 η = 1 and t = 2 log M / B t = \sqrt{2\log M/B} t = 2 log M / B for some tuning parameter B B B
Output: Retained indices K ^ n \widehat{\mathcal{K}}_n K n and CPDAG collection G ^ n \widehat{\mathcal{G}}_n G n
Initialize K ^ n ← ∅ \widehat{\mathcal{K}}_n \leftarrow\varnothing K n ← ∅ and G ^ n ← ∅ \widehat{\mathcal{G}}_n \leftarrow\varnothing G n ← ∅ ;
for m = 1 , … , M m = 1,\ldots,M m = 1 , … , M do
Run the PC algorithm with the following modified CI tests:
foreach C I CI C I test X i ⊥ ⊥ X j ∣ X S X_i \perp\!\!\!\perp X_j \mid X_S X i ⊥ ⊥ X j ∣ X S do
Draw ψ ^ i j ∣ S [ m ] ∼ N ( ψ ^ i j ∣ S , η 2 σ ^ i j ∣ S 2 ) \widehat{\psi}_{ij\mid S}^{[m]} \sim\mathcal{N}(\widehat{\psi}_{ij\mid S},\eta^2\widehat{\sigma}_{ij\mid S}^2) ψ ij ∣ S [ m ] ∼ N ( ψ ij ∣ S , η 2 σ ij ∣ S 2 ) ;
Reject independence if ∣ ψ ^ i j ∣ S [ m ] ∣ / σ ^ i j ∣ S > t |\widehat{\psi}_{ij\mid S}^{[m]}|/\widehat{\sigma}_{ij\mid S} > t ∣ ψ ij ∣ S [ m ] ∣/ σ ij ∣ S > t ;
Let G ^ n [ m ] \widehat{G}_n^{[m]} G n [ m ] denote the resulting graph;
if G ^ n [ m ] \widehat{G}_n^{[m]} G n [ m ] is a valid CPDAG then
K ^ n ← K ^ n ∪ { m } \widehat{\mathcal{K}}_n \leftarrow\widehat{\mathcal{K}}_n \cup\{m\} K n ← K n ∪ { m } ;
G ^ n ← G ^ n ∪ { G ^ n [ m ] } \widehat{\mathcal{G}}_n \leftarrow\widehat{\mathcal{G}}_n \cup\{\widehat{G}_n^{[m]}\} G n ← G n ∪ { G n [ m ] } ;
Analyzing the perturbed PC algorithm
We give conditions under which G ^ n \widehat{\mathcal{G}}_n G n contains G ⋆ G^\star G ⋆ (coverage) and under which it equals { G ⋆ } \{G^\star\} { G ⋆ } (collapse). We call a run correct if every conditional independence test it encounters is decided correctly. For the analysis, we use the stronger event that all tests l ∈ T l \in\mathcal{T} l ∈ T are decided correctly, including tests that may not be encountered by a particular run. Since ψ l = 0 \psi_l = 0 ψ l = 0 exactly when i i i and j j j are d-separated by S S S in G ⋆ G^\star G ⋆ , this event guarantees that the run follows the oracle PC path and returns G ⋆ G^\star G ⋆ .
A preliminary lemma
We begin with a general finite-sample bound, proved in Appendix § 12 .
Lemma 1. Let z : = z ν / 2 L z := z_{\nu/2L} z := z ν /2 L and, for t , η > 0 t,\eta> 0 t , η > 0 ,
π ( t , η ) : = { Φ ( t − z η ) − Φ ( − t − z η ) } L 0 ∏ l ∈ T n o n − n u l l Φ ( κ l − z − t η ) . \pi(t,\eta) := \left\{\Phi\left(\frac{t-z}{\eta}\right)-\Phi\left(\frac{-t-z}{\eta}\right)\right\}^{L_0}\prod_{l\in\mathcal{T}_{\mathrm{non-null}}}\Phi\left(\frac{\kappa_l-z-t}{\eta}\right). π ( t , η ) := { Φ ( η t − z ) − Φ ( η − t − z ) } L 0 l ∈ T non − null ∏ Φ ( η κ l − z − t ) .
On E n E_n E n and given data D \mathcal{D} D , each run of Algorithm 1 is correct with probability at least π : = π ( t , η ) \pi:= \pi(t,\eta) π := π ( t , η ) , independently across runs. Hence, for any sample size n n n ,
P ( G ⋆ ∈ G ^ n ) ≥ { 1 − ( 1 − π ) M } P ( E n ) , P ( G ^ n = { G ⋆ } ) ≥ π M P ( E n ) . \mathbb{P}(G^\star\in\widehat{\mathcal{G}}_n) \ge\{1-(1-\pi)^M\}\mathbb{P}(E_n), \qquad\mathbb{P}(\widehat{\mathcal{G}}_n=\{G^\star\}) \ge\pi^M\mathbb{P}(E_n). P ( G ⋆ ∈ G n ) ≥ { 1 − ( 1 − π ) M } P ( E n ) , P ( G n = { G ⋆ }) ≥ π M P ( E n ) .
Lemma 1 reduces both coverage and collapse to the probability that a single perturbed PC run is correct. The quantity π \pi π gives a lower bound on the single-run probability. Each factor in π \pi π lower bounds, on E n E_n E n , the probability that one perturbed conditional independence test makes the correct decision. The product arises from the independence of the perturbations across tests. Coverage is guaranteed when at least one of the M M M runs is correct, yielding the factor 1 − ( 1 − π ) M 1-(1-\pi)^M 1 − ( 1 − π ) M , whereas collapse is guaranteed when all M M M runs are correct, yielding π M \pi^M π M .
Asymptotic guarantees
Building on Lemma 1, we next give conditions on t t t , η \eta η and M M M that ensure asymptotic coverage and collapse. Let t = t n t=t_n t = t n , η = η n \eta=\eta_n η = η n and M = M n M=M_n M = M n be sequences that may depend on n n n , and write π n = π ( t n , η n ) \pi_n=\pi(t_n,\eta_n) π n = π ( t n , η n ) . For δ n ∈ ( 0 , 1 ) \delta_n\in(0,1) δ n ∈ ( 0 , 1 ) , define the global reach
ω n : = η n Φ − 1 ( 1 / 2 + ( 1 − δ n ) 1 / ( L M n ) / 2 ) . \omega_n := \eta_n\Phi^{-1}\left(1/2+(1-\delta_n)^{1/(LM_n)}/2\right). ω n := η n Φ − 1 ( 1/2 + ( 1 − δ n ) 1/ ( L M n ) /2 ) .
For test l l l in run m m m ,
T ^ l [ m ] = ∣ ψ l σ l + U ^ l + U ^ l [ m ] ∣ , where U ^ l [ m ] : = ψ ^ l [ m ] − ψ ^ l σ l . (3) \widehat{T}_l^{[m]}=\left|\frac{\psi_l}{\sigma_l}+\widehat{U}_l+\widehat{U}_l^{[m]}\right|,\qquad\text{where }\widehat{U}_l^{[m]}:=\frac{\widehat{\psi}_l^{[m]}-\widehat{\psi}_l}{\sigma_l}. \tag*{(3)} T l [ m ] = σ l ψ l + U l + U l [ m ] , where U l [ m ] := σ l ψ l [ m ] − ψ l . (3)
Given the data, the perturbations U ^ l [ m ] \widehat{U}_l^{[m]} U l [ m ] are independent N ( 0 , η n 2 ) \mathcal{N}(0,\eta_n^2) N ( 0 , η n 2 ) across tests and runs. By construction,
P ( max m ≤ M n , l ≤ L ∣ U ^ l [ m ] ∣ ≤ ω n ) = 1 − δ n . \mathbb{P}\left(\max_{m\le M_n,\;l\le L}|\widehat{U}_l^{[m]}|\le\omega_n\right)=1-\delta_n. P ( m ≤ M n , l ≤ L max ∣ U l [ m ] ∣ ≤ ω n ) = 1 − δ n .
Thus, with probability 1 − δ n 1-\delta_n 1 − δ n , every perturbation across all tests and runs has magnitude at most ω n \omega_n ω n . For an integer s ≥ 1 s\ge1 s ≥ 1 , define the joint favorable reach
r n ( s ) : = η n Φ − 1 ( 1 − ( 1 − δ n 1 / M n ) 1 / s ) . r_n(s):=\eta_n\Phi^{-1}\left(1-\left(1-\delta_n^{1/M_n}\right)^{1/s}\right). r n ( s ) := η n Φ − 1 ( 1 − ( 1 − δ n 1/ M n ) 1/ s ) .
We define r n ( 0 ) = 0 r_n(0)=0 r n ( 0 ) = 0 . Then for any specified set W ⊆ T n o n − n u l l W\subseteq\mathcal{T}_{\mathrm{non-null}} W ⊆ T non − null of s s s nonnull tests,
P ( ∃ m ≤ M n : min l ∈ W U l [ m ] ≥ r n ( s ) ) = 1 − δ n . \mathbb{P}\left(\exists m\le M_n:\min_{l\in W}U_l^{[m]}\ge r_n(s)\right)=1-\delta_n. P ( ∃ m ≤ M n : l ∈ W min U l [ m ] ≥ r n ( s ) ) = 1 − δ n .
Thus, with probability 1 − δ n 1-\delta_n 1 − δ n , some run has perturbations of at least r n ( s ) r_n(s) r n ( s ) for all tests in W W W .
The distinction between ω n \omega_n ω n and r n ( s ) r_n(s) r n ( s ) is important. The global reach ω n \omega_n ω n describes the largest perturbation that can occur anywhere in the entire collection of runs, and is therefore the relevant quantity for collapse: to ensure every run is correct, even the most adverse perturbation must not change any decision. In contrast, r n ( s ) r_n(s) r n ( s ) is relevant for coverage: it measures how far a single run can simultaneously move s s s specified nonnull tests in the favorable direction. If some nonnull statistics do not clear the threshold on their own, such a favorable run can shift them above the threshold simultaneously. See Figure 6 for an illustration.
Figure 6. Global and joint favorable reach for two nonnull tests. All displayed signed statistics are positive and hence coincide with their absolute values. The dot marks the observed pair, crosses illustrate perturbed runs, and shading indicates joint rejection. The square has half-width ω n \omega_n ω n ; the blue arrow has displacement ( r n ( 2 ) , r n ( 2 ) ) (r_n(2),r_n(2)) ( r n ( 2 ) , r n ( 2 )) , with the black cross illustrating a run beyond its tip in both coordinates. On the respective reach events, each of probability at least 1 − δ n 1-\delta_n 1 − δ n , (a) every run rejects both tests and (b) at least one run rejects both. In (c), individual rejections occur in different illustrated runs, while simultaneous rejection requires an increase greater than r n ( 2 ) r_n(2) r n ( 2 ) in each coordinate.
For coverage, only the nonnull tests whose signals do not clear the threshold by a diverging margin need favorable perturbations. This motivates separating the nonnull tests according to whether they asymptotically lie above the threshold.
Definition 9 (Strong and weak tests). A nonnull test l ∈ T n o n − n u l l l\in\mathcal{T}_{\mathrm{non-null}} l ∈ T non − null is called strong if κ l − t n → ∞ \kappa_l-t_n\to\infty κ l − t n → ∞ as n → ∞ n\to\infty n → ∞ , and weak otherwise.
Let L w e a k L_{\mathrm{weak}} L weak denote the number of weak tests in T n o n − n u l l \mathcal{T}_{\mathrm{non-null}} T non − null . When δ n ≤ 1 / 2 \delta_n\le1/2 δ n ≤ 1/2 , we have that r n ( s ) ≤ ω n r_n(s)\le\omega_n r n ( s ) ≤ ω n . Moreover, if M n → ∞ M_n\to\infty M n → ∞ , δ n → 0 \delta_n\to0 δ n → 0 and log ( 1 / δ n ) = o ( log M n ) \log(1/\delta_n)=o(\log M_n) log ( 1/ δ n ) = o ( log M n ) , then
ω n = ( 1 + o ( 1 ) ) η n 2 log M n , r n ( L w e a k ) = ( 1 + o ( 1 ) ) η n 2 log M n L w e a k . \omega_n=(1+o(1))\eta_n\sqrt{2\log M_n},\qquad r_n(L_{\mathrm{weak}})=(1+o(1))\eta_n\sqrt{\frac{2\log M_n}{L_{\mathrm{weak}}}}. ω n = ( 1 + o ( 1 )) η n 2 log M n , r n ( L weak ) = ( 1 + o ( 1 )) η n L weak 2 log M n .
Thus, coordinating favorable perturbations across all L w e a k > 0 L_{\mathrm{weak}}>0 L weak > 0 weak tests reduces the available reach by an asymptotic factor 1 / L w e a k \sqrt{1/L_{\mathrm{weak}}} 1/ L weak relative to the global reach.
Theorem 2 (Coverage and collapse). Suppose η ‾ ≤ η n ≤ η ‾ \underline{\eta}\le\eta_n\le\overline{\eta} η ≤ η n ≤ η for constants η ‾ , η ‾ > 0 \overline{\eta},\underline{\eta}>0 η , η > 0 , fix 0 < ν < 1 0<\nu<1 0 < ν < 1 and let δ n → 0 \delta_n\to0 δ n → 0 . Then:
(a) Coverage. lim inf n P ( G ∗ ∈ G ^ n ) ≥ 1 − ν \liminf_n\mathbb{P}(\mathcal{G}^*\in\widehat{\mathcal{G}}_n)\ge1-\nu lim inf n P ( G ∗ ∈ G n ) ≥ 1 − ν if either of these two conditions holds:
(i) t n t_n t n is bounded, and M n t n L 0 → ∞ M_nt_n^{L_0}\to\infty M n t n L 0 → ∞ as n → ∞ n\to\infty n → ∞ ;
(ii) t n → ∞ t_n\to\infty t n → ∞ as n → ∞ n\to\infty n → ∞ , and every nonnull weak test l l l satisfies κ l − t n + r n ( L w e a k ) → ∞ \kappa_l-t_n+r_n(L_{\mathrm{weak}})\to\infty κ l − t n + r n ( L weak ) → ∞ .
(b) Collapse. lim inf n P ( { G ⋆ } = G ^ n ) ≥ 1 − ν \liminf_{n} \mathbb{P}(\{G^\star\}=\widehat{G}_n) \ge1-\nu lim inf n P ({ G ⋆ } = G n ) ≥ 1 − ν if t n − ω n → ∞ t_n-\omega_n\to\infty t n − ω n → ∞ as n → ∞ n\to\infty n → ∞ and κ min , n − t n − ω n → ∞ \kappa_{\min,n}-t_n-\omega_n\to\infty κ m i n , n − t n − ω n → ∞ as n → ∞ n\to\infty n → ∞ .
We prove Theorem 2 in Appendix § 12 .
Interpreting the theorem
Part (a) gives two routes to coverage. In part (a)(i), the threshold remains bounded. Null statistics can therefore cross the threshold with nonnegligible probability, leading to substantial variability in the estimated graphs across runs. Nevertheless, each run has a nonvanishing probability of returning a true CPDAG, and sufficiently many independent runs make it likely that at least one run is correct.
In part (a)(ii), the threshold grows with the number of runs. Null statistics are then increasingly unlikely to cross the threshold, reducing variability in the estimated graphs due to null tests. The main difficulty shifts to the weak nonnull signals. Coverage requires these signals to remain close enough to the threshold that favorable perturbations (i.e., r n ( L w e a k ) r_n(L_{\mathrm{weak}}) r n ( L weak ) ) can push them across in at least one run. Strong signals already exceed the threshold by a diverging margin and therefore do not rely on favorable perturbations.
Part (b) gives a stronger requirement for collapse. Every null statistic must lie below the threshold for every run, while every nonnull statistic must remain above it. The threshold must therefore dominate the largest null perturbation (i.e., ω n \omega_n ω n ), and the weakest nonnull signal must exceed the threshold by more than the largest perturbation.
The goals of coverage and collapse impose different signal requirements. Perturbations help coverage because a favorable run can reveal a signal, but they make collapse harder because not every run must be correct. Without a quantitative lower bound on the nonzero signals, no tuning can guarantee both coverage and collapse uniformly over faithful distributions. This agrees with the impossibility of uniform consistency for CPDAG estimation ([41 , 63 ] ).
We next consider three threshold regimes.
Default: reach-scaled threshold
We take
η n = 1 , t n = 2 log M n B . \eta_n=1,\qquad t_n=\sqrt{\frac{2\log M_n}{B}}. η n = 1 , t n = B 2 log M n .
where B > 0 B>0 B > 0 is a tuning parameter. Since ω n = ( 1 + o ( 1 ) ) 2 log M n \omega_n=(1+o(1))\sqrt{2\log M_n} ω n = ( 1 + o ( 1 )) 2 log M n for large M n M_n M n , the threshold remains a fixed fraction 1 / B 1/\sqrt{B} 1/ B of the global reach as M n M_n M n grows. If L w e a k = 0 L_{\mathrm{weak}}=0 L weak = 0 , Theorem 2(a)(ii) gives coverage for every B > 0 B>0 B > 0 . Otherwise, for large M n M_n M n
r n ( L w e a k ) − t n = ( 1 + o ( 1 ) L w e a k − 1 B ) 2 log M n . r_n(L_{\mathrm{weak}})-t_n=\left(\frac{1+o(1)}{\sqrt{L_{\mathrm{weak}}}}-\frac{1}{\sqrt{B}}\right)\sqrt{2\log M_n}. r n ( L weak ) − t n = ( L weak 1 + o ( 1 ) − B 1 ) 2 log M n .
Thus, if B > L w e a k B>L_{\mathrm{weak}} B > L weak , this difference diverges, so every weak test satisfies the condition of Theorem 2(a)(ii). Hence, B B B determines how many weak tests the coverage guarantee can accommodate. In particular, B > L 1 B>L_1 B > L 1 requires no lower bound on the nonzero partial correlations.
For B > 1 B>1 B > 1 , t n − ω n → − ∞ t_n-\omega_n\to-\infty t n − ω n → − ∞ , so the collapse condition in part (b) of Theorem 2 fails. Null statistics can cross the threshold in some runs, so the collection need not collapse. Larger B B B lowers the threshold, which improves weak-signal recovery at the cost of more false rejections of conditional independence; smaller B B B does the reverse.
Remark 2 (Choosing B B B in practice). We use 75% of the data to construct, for each candidate value of B B B , the collection of CPDAGs returned by perturbed PC. For each collection, we compute the largest Gaussian likelihood attained by any graph in the collection. We then choose the smallest B B B whose best likelihood is within 1% of the largest likelihood achieved over all candidate values of B B B . This favors the least aggressive perturbation level that still recovers a graph with a near-optimal fit.
Collapse-oriented threshold
Alternatively, take t n = c 2 log n t_n=c\sqrt{2\log n} t n = c 2 log n and η n = 1 \eta_n=1 η n = 1 for any fixed c > 0 c>0 c > 0 , with a fixed number of runs. Then, ω n = O ( 1 ) \omega_n=O(1) ω n = O ( 1 ) so both coverage and collapse hold whenever κ min , n − c 2 log n → ∞ \kappa_{\min,n}-c\sqrt{2\log n}\to\infty κ m i n , n − c 2 log n → ∞ . In particular, it is sufficient that κ min , n / log n → ∞ \kappa_{\min,n}/\sqrt{\log n}\to\infty κ m i n , n / log n → ∞ , or equivalently, ρ min , n n / log n → ∞ \rho_{\min,n}\sqrt{n}/\sqrt{\log n}\to\infty ρ m i n , n n / log n → ∞ . Thus, the minimum nonzero partial correlation may decay nearly as fast as log n / n \sqrt{\log n/n} log n / n . This is the consistency regime: collapse is possible, but it requires a quantitative signal-separation condition analogous to strong faithfulness.
For a fixed number of nodes p p p , this condition is weaker than Assumption (A4) of Kalisch and Bühlmann [24 ] , which requires O ( n ξ ) ≤ ρ min , n O(n^{\xi}) \le\rho_{\min,n} O ( n ξ ) ≤ ρ m i n , n for some ξ < 1 / 2 \xi< 1/2 ξ < 1/2 .
Bounded threshold and the tuning of Chang et al. (2026)
Part (a)(i) gives a third route to coverage. Suppose t n t_n t n is bounded and η n \eta_n η n is bounded above and away from zero. Then the nonnull factors in π \pi π are bounded below by positive constants, while the null factors are of order t n t_n t n . Hence, π n ≍ t n L 0 \pi_n \asymp t_n^{L_0} π n ≍ t n L 0 . Given data D \mathcal D D for which E n E_n E n holds, the runs are independent, and the probability that G ∗ \mathcal G^* G ∗ is returned in at least one of the M n M_n M n runs is at least 1 − exp { − M n π n } 1-\exp\{-M_n\pi_n\} 1 − exp { − M n π n } . Therefore, M n t n L 0 → ∞ M_n t_n^{L_0} \to\infty M n t n L 0 → ∞ is sufficient for coverage without a quantitative lower bound on the nonzero signals. The tuning of Chang et al. [4 ] is a special case: η = 1 \eta=1 η = 1 , M n ≥ log n M_n \ge\log n M n ≥ log n and t n = c ∗ ( log n / M n ) 1 / L ≤ c ∗ z ν / 2 L t_n = c^*(\log n/M_n)^{1/L} \le c^* z_{\nu/2L} t n = c ∗ ( log n / M n ) 1/ L ≤ c ∗ z ν /2 L for some c ∗ > 0 c^*>0 c ∗ > 0 with c ∗ ( log n / M n ) 1 / L ≤ 1 c^*(\log n/M_n)^{1/L} \le1 c ∗ ( log n / M n ) 1/ L ≤ 1 . Since x L 0 / L ≥ x x^{L_0/L} \ge x x L 0 / L ≥ x for 0 < x ≤ 1 0<x\le1 0 < x ≤ 1 , M n t n L 0 ≥ ( c ∗ z ν / 2 L ) L 0 log n → ∞ M_n t_n^{L_0} \ge(c^* z_{\nu/2L})^{L_0}\log n \to\infty M n t n L 0 ≥ ( c ∗ z ν /2 L ) L 0 log n → ∞ .
Remark 3. The threshold of Chang et al. [4 ] and our default threshold have fundamentally different scaling. Since c ∗ ( log n / M n ) 1 / L ≤ 1 c^*(\log n/M_n)^{1/L}\le1 c ∗ ( log n / M n ) 1/ L ≤ 1 , their threshold is at most z ν / 2 L z_{\nu/2L} z ν /2 L and therefore remains bounded in M n M_n M n . Our default threshold instead grows on the order of log M n \sqrt{\log M_n} log M n . Thus, no fixed choice of c ∗ c^* c ∗ can make the two thresholds comparable for large M n M_n M n .
Both thresholds permit coverage without a lower bound on the nonzero signals. Their different scaling, however, leads to different behavior under the null. The largest perturbation of a null standardized test statistic is of order log M n \sqrt{\log M_n} log M n , while the threshold of Chang et al. [4 ] remains bounded. Null statistics therefore cross the threshold in some runs with high probability, producing denser graphs and greater variability in the retained collection. See experimental results in § 7 .
Constructing our confidence regions
While Theorem 2 gives asymptotic coverage for G ^ n \widehat{\mathbb G}_n G n , two challenges remain. First, at moderate sample sizes, the collection may fail to contain the true CPDAG, especially when the signals are weak. Second, even with adequate coverage, a large collection of CPDAGs can be difficult to interpret. We therefore use G ^ n \widehat{\mathbb G}_n G n to construct the confidence balls and intervals of Definitions 6 and 7. These regions enlarge the collection to improve the coverage, and they summarize graph uncertainty in a concise form: a center and a radius, or a lower and an upper graph.
To construct the ball, we first estimate a center G ^ 0 , n \widehat{\mathcal G}_{0,n} G 0 , n by applying PC to the unperturbed test statistics with threshold 2 log n \sqrt{2\log n} 2 log n . This threshold diverges slowly enough to retain power against nonzero partial correlations while driving false rejections of conditional independence to zero. We then use G ^ n \widehat{\mathbb G}_n G n to define the confidence ball as:
G ^ n b a l l : = { G ∈ G : d m o d e l ( G , G ^ 0 , n ) ≤ r ^ n } with r ^ n : = max m ∈ K ^ n d m o d e l ( G ^ n [ m ] , G ^ 0 , n ) , (4) \widehat{\mathbb G}^{\mathrm{ball}}_n := \left\{\mathcal G \in\mathbb G : d_{\mathrm{model}}(\mathcal G,\widehat{\mathcal G}_{0,n}) \le\widehat r_n\right\}
\quad\text{with}\quad
\widehat r_n := \max_{m\in\widehat{\mathcal K}_n} d_{\mathrm{model}}(\widehat{\mathcal G}^{[m]}_n,\widehat{\mathcal G}_{0,n}), \tag*{(4)} G n ball := { G ∈ G : d model ( G , G 0 , n ) ≤ r n } with r n := m ∈ K n max d model ( G n [ m ] , G 0 , n ) , (4)
which is the collection of graphs within model-oriented distance r ^ n \widehat r_n r n from the center G ^ 0 , n \widehat{\mathcal G}_{0,n} G 0 , n . Here, r ^ n \widehat r_n r n is the maximum distance from the center to a graph in the collection G ^ n \widehat{\mathbb G}_n G n .
Using G ^ n \widehat{\mathbb G}_n G n , we construct the confidence interval as:
G ^ n i n t e r v a l : = { G ∈ G : G ^ n , L ⪯ G ⪯ G ^ n , U } where G ^ n , L ⪯ G ^ n [ m ] and G ^ n [ m ] ⪯ G ^ n , U ∀ m ∈ K ^ n . (5) \widehat{\mathbb G}^{\mathrm{interval}}_n := \left\{\mathcal G \in\mathbb G : \widehat{\mathcal G}_{n,L} \preceq\mathcal G \preceq\widehat{\mathcal G}_{n,U}\right\}
\quad\text{where}\quad
\widehat{\mathcal G}_{n,L} \preceq\widehat{\mathcal G}^{[m]}_n
\quad\text{and}\quad
\widehat{\mathcal G}^{[m]}_n \preceq\widehat{\mathcal G}_{n,U}\ \ \forall m\in\widehat{\mathcal K}_n. \tag*{(5)} G n interval := { G ∈ G : G n , L ⪯ G ⪯ G n , U } where G n , L ⪯ G n [ m ] and G n [ m ] ⪯ G n , U ∀ m ∈ K n . (5)
This region contains all CPDAGs lying in between G ^ n , L \widehat{\mathcal G}_{n,L} G n , L and G ^ n , U \widehat{\mathcal G}_{n,U} G n , U in the partial order, where G ^ n , L \widehat{\mathcal G}_{n,L} G n , L is any lower bound on all graphs in G ^ n \widehat{\mathbb G}_n G n , and G ^ n , U \widehat{\mathcal G}_{n,U} G n , U is any upper bound. Such bounds always exist: one may take G ^ n , L \widehat{\mathcal G}_{n,L} G n , L to be the empty CPDAG, the least element in the CPDAG poset, and G ^ n , U \widehat{\mathcal G}_{n,U} G n , U to be the fully connected CPDAG, the greatest element. We therefore seek bounds that make the interval narrow, as measured by rank ( G ^ n , U ) − rank ( G ^ n , L ) \operatorname{rank}(\widehat{\mathcal G}_{n,U})-\operatorname{rank}(\widehat{\mathcal G}_{n,L}) rank ( G n , U ) − rank ( G n , L ) . We will describe some strategies in § 6 .
By construction, G ^ n ⊆ G ^ n b a l l \widehat{\mathbb G}_n \subseteq\widehat{\mathbb G}^{\mathrm{ball}}_n G n ⊆ G n ball and G ^ n ⊆ G ^ n i n t e r v a l \widehat{\mathbb G}_n \subseteq\widehat{\mathbb G}^{\mathrm{interval}}_n G n ⊆ G n interval . The following corollary therefore follows directly from Theorem 2.
Corollary 1. Suppose the conditions for coverage hold from Theorem 2. Then, we have that G ^ n b a l l \widehat{\mathbb G}^{\mathrm{ball}}_n G n ball and G ^ n i n t e r v a l \widehat{\mathbb G}^{\mathrm{interval}}_n G n interval are asymptotically valid confidence regions, i.e.,
lim inf n P ( G ∗ ∈ G ^ n b a l l ) ≥ 1 − ν and lim inf n P ( G ∗ ∈ G ^ n i n t e r v a l ) ≥ 1 − ν . \liminf_{n}\mathbb P(\mathcal G^* \in\widehat{\mathbb G}^{\mathrm{ball}}_n) \ge1-\nu
\quad\text{and}\quad
\liminf_{n}\mathbb P(\mathcal G^* \in\widehat{\mathbb G}^{\mathrm{interval}}_n) \ge1-\nu. n lim inf P ( G ∗ ∈ G n ball ) ≥ 1 − ν and n lim inf P ( G ∗ ∈ G n interval ) ≥ 1 − ν .
Algorithm 2 provides full details for constructing G ^ n b a l l \widehat{\mathbb G}^{\mathrm{ball}}_n G n ball and G ^ n i n t e r v a l \widehat{\mathbb G}^{\mathrm{interval}}_n G n interval .
Algorithm 2: Confidence ball and interval
Input: ( K ^ n , G ^ n ) (\widehat{\mathcal{K}}_n,\widehat{\mathcal{G}}_n) ( K n , G n ) from Algorithm 1
Output: Ball G ^ n b a l l \widehat{\mathcal{G}}_n^{\mathrm{ball}} G n ball and interval G ^ n i n t e r v a l \widehat{\mathcal{G}}_n^{\mathrm{interval}} G n interval
Run PC with threshold 2 log n \sqrt{2\log n} 2 log n to get the center G ^ 0 , n \widehat{G}_{0,n} G 0 , n ;
r ^ n ← max m ∈ K ^ n d m o d e l ( G ^ 0 , n , G ^ n [ m ] ) ; \widehat{r}_n \leftarrow\max_{m\in\widehat{\mathcal{K}}_n}d_{\mathrm{model}}(\widehat{G}_{0,n},\widehat{G}_n^{[m]}); r n ← max m ∈ K n d model ( G 0 , n , G n [ m ] ) ;
G ^ n b a l l ← { G : d m o d e l ( G , G ^ 0 , n ) ≤ r ^ n } ; \widehat{\mathcal{G}}_n^{\mathrm{ball}} \leftarrow\{G:d_{\mathrm{model}}(G,\widehat{G}_{0,n})\leq\widehat{r}_n\}; G n ball ← { G : d model ( G , G 0 , n ) ≤ r n } ;
G ^ n , L ← \widehat{G}_{n,L}\leftarrow G n , L ← CPDAG that satisfies G ^ n , L ⪯ G \widehat{G}_{n,L}\preceq G G n , L ⪯ G for all G ∈ G ^ n G\in\widehat{\mathcal{G}}_n G ∈ G n ;
G ^ n , U ← \widehat{G}_{n,U}\leftarrow G n , U ← CPDAG that satisfies G ⪯ G ^ n , U G\preceq\widehat{G}_{n,U} G ⪯ G n , U for all G ∈ G ^ n G\in\widehat{\mathcal{G}}_n G ∈ G n ;
G ^ n i n t e r v a l ← { G : G ^ n , L ⪯ G ⪯ G ^ n , U } ; \widehat{\mathcal{G}}_n^{\mathrm{interval}}\leftarrow\{G:\widehat{G}_{n,L}\preceq G\preceq\widehat{G}_{n,U}\}; G n interval ← { G : G n , L ⪯ G ⪯ G n , U } ;
Theoretical results for computation
The confidence interval of § 4.3 requires common lower and upper graphs of the retained collection. The confidence ball requires model-oriented distances from the center to each retained graph. Finding the narrowest interval or computing exact distances in general requires searching over the CPDAG poset. This section develops bounds to guide these searches. § 5.1 bounds the rank of the smallest common upper graph and the largest common lower graph. § 5.2 gives exact distances for structured pairs. § 5.3 provides bounds on the model-oriented distance, which partially uses the results from the previous two subsections. The theoretical results in this section are useful for the algorithms developed for obtaining confidence regions in § 6 .
Throughout, we denote a pair of CPDAGs of interest by G s \mathcal{G}_s G s and G t \mathcal{G}_t G t , and use the shorthand notation d = d m o d e l d=d_{\mathrm{model}} d = d model .
Bounds for common lower and upper graphs
Let G ^ n ⊆ G \widehat{\mathcal{G}}_n\subseteq\mathcal{G} G n ⊆ G be a collection of CPDAGs obtained from Algorithm 1. As described in Algorithm 2, for building a confidence interval, we seek a lower graph G ^ n , L ∈ G \widehat{G}_{n,L}\in\mathcal{G} G n , L ∈ G and upper graph G ^ n , U ∈ G \widehat{G}_{n,U}\in\mathcal{G} G n , U ∈ G satisfying G ^ n , L ⪯ G ⪯ G ^ n , U \widehat{G}_{n,L}\preceq G\preceq\widehat{G}_{n,U} G n , L ⪯ G ⪯ G n , U for all G ∈ G ^ n G\in\widehat{\mathcal{G}}_n G ∈ G n . The width of this interval is given by rank ( G ^ n , U ) − rank ( G ^ n , L ) \operatorname{rank}(\widehat{G}_{n,U})-\operatorname{rank}(\widehat{G}_{n,L}) rank ( G n , U ) − rank ( G n , L ) . To obtain these two graphs, our algorithm (described in § 6 ) constructs these graphs sequentially by finding common lower and upper graphs for pairs of CPDAGs. To keep the final interval narrow, we seek the largest-rank common lower graph and the smallest-rank common upper graph for any pair G s , G t ∈ G \mathcal{G}_s,\mathcal{G}_t\in\mathcal{G} G s , G t ∈ G :
arg max G ∈ G : G ⪯ G s , G ⪯ G t rank ( G ) and arg min G ∈ G : G s ⪯ G , G t ⪯ G rank ( G ) . \underset{G\in\mathcal{G}:G\preceq\mathcal{G}_s,G\preceq\mathcal{G}_t}{\arg\max}\ \operatorname{rank}(G)
\qquad\text{and}\qquad
\underset{G\in\mathcal{G}:\mathcal{G}_s\preceq G,\mathcal{G}_t\preceq G}{\arg\min}\ \operatorname{rank}(G). G ∈ G : G ⪯ G s , G ⪯ G t arg max rank ( G ) and G ∈ G : G s ⪯ G , G t ⪯ G arg min rank ( G ) .
These optimization problems are well-defined as the empty graph G e m p t y \mathcal{G}_{\mathrm{empty}} G empty is always a feasible graph in the first optimization and the fully connected graph G f u l l \mathcal{G}_{\mathrm{full}} G full is always feasible in the second optimization problem. To solve these optimization problems, the procedures described in § 6 require bounds on the maximum and minimum objective values of the optimization problem above. We first define:
ρ L ( G s , G t ) : = max G ∈ G : G ⪯ G s , G ⪯ G t rank ( G ) and ρ U ( G s , G t ) : = min G ∈ G : G s ⪯ G , G t ⪯ G rank ( G ) . \rho_L(\mathcal{G}_s,\mathcal{G}_t):=\max_{G\in\mathcal{G}:G\preceq\mathcal{G}_s,G\preceq\mathcal{G}_t}\operatorname{rank}(G)
\qquad\text{and}\qquad
\rho_U(\mathcal{G}_s,\mathcal{G}_t):=\min_{G\in\mathcal{G}:\mathcal{G}_s\preceq G,\mathcal{G}_t\preceq G}\operatorname{rank}(G). ρ L ( G s , G t ) := G ∈ G : G ⪯ G s , G ⪯ G t max rank ( G ) and ρ U ( G s , G t ) := G ∈ G : G s ⪯ G , G t ⪯ G min rank ( G ) .
§ 5.1.1 develops lower and upper bounds for ρ L ( G s , G t ) \rho_L(\mathcal{G}_s,\mathcal{G}_t) ρ L ( G s , G t ) . Section 5.1.2 develops bounds for ρ U ( G s , G t ) \rho_U(\mathcal{G}_s,\mathcal{G}_t) ρ U ( G s , G t ) . Each subsection constructs a feasible common graph and bounds the best achievable rank. The constructed graphs provide feasible interval endpoints, while the remaining bounds limit how much their ranks can improve during the search of § 6.6 . We use the following notation:
D ∩ ( G s , G t ) \mathcal{D}_{\cap}(\mathcal{G}_s,\mathcal{G}_t) D ∩ ( G s , G t ) is the intersection of chosen DAG representatives of G s \mathcal{G}_s G s and G t \mathcal{G}_t G t ;
Skel ∩ ( G s , G t ) \operatorname{Skel}_{\cap}(\mathcal{G}_s,\mathcal{G}_t) Skel ∩ ( G s , G t ) and Skel ∪ ( G s , G t ) \operatorname{Skel}_{\cup}(\mathcal{G}_s,\mathcal{G}_t) Skel ∪ ( G s , G t ) are the intersection and union of their skeletons;
G c h ( G s , G t ) \mathcal{G}_{\mathrm{ch}}(\mathcal{G}_s,\mathcal{G}_t) G ch ( G s , G t ) is a chordal completion of the union of the moral graphs of G s \mathcal{G}_s G s and G t \mathcal{G}_t G t .
Bounds for constructing a common lower graph
For the confidence interval, we want a common lower graph with rank as large as possible, since a larger lower endpoint produces a narrower interval. For a pair G s , G t \mathcal{G}_s,\mathcal{G}_t G s , G t , this means determining how many edges can be retained while remaining below both graphs. We first construct a feasible common lower graph, which gives a lower bound on ρ L ( G s , G t ) \rho_L(\mathcal{G}_s,\mathcal{G}_t) ρ L ( G s , G t ) , and then identify edge conflicts that limit how large any common lower graph can be.
A simple feasible construction comes from intersecting DAG representatives. The DAG D ∩ ( G s , G t ) \mathcal{D}_{\cap}(G_s,G_t) D ∩ ( G s , G t ) is a subgraph of the chosen DAG representatives of G s G_s G s and G t G_t G t . Hence, the CPDAG of D ∩ ( G s , G t ) \mathcal{D}_{\cap}(G_s,G_t) D ∩ ( G s , G t ) is a common lower graph, giving
∣ E ( D ∩ ( G s , G t ) ) ∣ ≤ ρ L ( G s , G t ) . |E(\mathcal{D}_{\cap}(G_s,G_t))| \le\rho_L(G_s,G_t). ∣ E ( D ∩ ( G s , G t )) ∣ ≤ ρ L ( G s , G t ) .
Here, E ( ⋅ ) E(\cdot) E ( ⋅ ) denotes the edge set of the input graph. The quality of this bound depends on the chosen representatives. For example, if both CPDAGs consist of the undirected edge u − v u-v u − v , opposite orientations of their DAG representatives give an empty intersection, whereas matching orientations retain the edge. Thus, the choice of representatives affects the tightness of the bound, but not its validity.
To upper bound ρ L ( G s , G t ) \rho_L(G_s,G_t) ρ L ( G s , G t ) , we ask which shared edges cannot be retained simultaneously. Every common lower graph has its skeleton inside Skel ∩ ( G s , G t ) \operatorname{Skel}_{\cap}(G_s,G_t) Skel ∩ ( G s , G t ) , but orientation differences can force some of these shared edges to be deleted. The simplest example is
G s : u → w ← v , G t : u − w − v . G_s:u\to w\leftarrow v,\qquad G_t:u-w-v. G s : u → w ← v , G t : u − w − v .
The collider implies marginal independence of u u u and v v v , whereas the chain implies independence conditional on w w w . Any common lower graph must satisfy both constraints, so it must delete at least one of the two shared edges. The following definition identifies this type of conflict inside larger graphs.
Definition 10 (Forbidden triple, legs, and shields). Let v - str ( G ) v\text{-}\operatorname{str}(G) v - str ( G ) denote the set of triples ( u , w , v ) (u,w,v) ( u , w , v ) that form a v v v -structure at w w w in G G G . The set of forbidden triples is
S ( G s , G t ) : = { ( u , w , v ) ∈ V 3 : { u , w } , { v , w } ∈ Skel ( G s ) ∩ Skel ( G t ) , { u , v } ∉ Skel ( G s ) ∪ Skel ( G t ) , ( u , w , v ) ∈ v - str ( G s ) △ v - str ( G t ) } . S(G_s,G_t):=\left\{(u,w,v)\in V^3:
\begin{array}{l}
\{u,w\},\{v,w\}\in\operatorname{Skel}(G_s)\cap\operatorname{Skel}(G_t),\\
\{u,v\}\notin\operatorname{Skel}(G_s)\cup\operatorname{Skel}(G_t),\\
(u,w,v)\in v\text{-}\operatorname{str}(G_s)\mathbin{\triangle}v\text{-}\operatorname{str}(G_t)
\end{array}
\right\}. S ( G s , G t ) := ⎩ ⎨ ⎧ ( u , w , v ) ∈ V 3 : { u , w } , { v , w } ∈ Skel ( G s ) ∩ Skel ( G t ) , { u , v } ∈ / Skel ( G s ) ∪ Skel ( G t ) , ( u , w , v ) ∈ v - str ( G s ) △ v - str ( G t ) ⎭ ⎬ ⎫ . For each forbidden triple ( u , w , v ) (u,w,v) ( u , w , v ) , where the order of u u u and v v v is irrelevant, { u , w } \{u,w\} { u , w } and { v , w } \{v,w\} { v , w } are its legs. The missing outer pair { u , v } \{u,v\} { u , v } is its shield.
Each forbidden triple requires at least one of its two legs to be omitted from any common lower graph. Because one omitted edge may resolve several forbidden triples, the edge-deletion requirements can overlap. We capture this overlap with an auxiliary conflict graph.
Definition 11 (Skeleton conflict graph). The skeleton conflict graph Γ L ( G s , G t ) \Gamma_L(G_s,G_t) Γ L ( G s , G t ) is an undirected graph with vertex set Skel ∩ ( G s , G t ) \operatorname{Skel}_{\cap}(G_s,G_t) Skel ∩ ( G s , G t ) . Two vertices are adjacent if the corresponding shared skeleton edges are the two legs of a forbidden triple.
Vertices of Γ L ( G s , G t ) \Gamma_L(G_s,G_t) Γ L ( G s , G t ) therefore represent shared edges that could potentially appear in a common lower graph, while edges of Γ L ( G s , G t ) \Gamma_L(G_s,G_t) Γ L ( G s , G t ) represent pairs that cannot be retained together. The shared edges omitted by any common lower graph must therefore form a vertex cover of Γ L ( G s , G t ) \Gamma_L(G_s,G_t) Γ L ( G s , G t ) . If τ ( Γ L ( G s , G t ) ) \tau(\Gamma_L(G_s,G_t)) τ ( Γ L ( G s , G t )) denotes the minimum vertex-cover size, then
ρ L ( G s , G t ) ≤ ∣ Skel ∩ ( G s , G t ) ∣ − τ ( Γ L ( G s , G t ) ) . \rho_L(G_s,G_t)\leq|\operatorname{Skel}_{\cap}(G_s,G_t)|-\tau(\Gamma_L(G_s,G_t)). ρ L ( G s , G t ) ≤ ∣ Skel ∩ ( G s , G t ) ∣ − τ ( Γ L ( G s , G t )) .
This bound caps the rank of every common lower graph, but computing a minimum vertex cover is NP-hard [25 ] .
For the search algorithm, we therefore also want a weaker bound that can be computed quickly. A maximum matching provides such a bound. A matching of Γ L ( G s , G t ) \Gamma_L(G_s,G_t) Γ L ( G s , G t ) is a set of edges with no shared endpoints, and a maximum matching of Γ L ( G s , G t ) \Gamma_L(G_s,G_t) Γ L ( G s , G t ) has the largest possible size, denoted by
ν ( Γ L ( G s , G t ) ) . \nu(\Gamma_L(G_s,G_t)). ν ( Γ L ( G s , G t )) .
Since every matched edge requires a distinct vertex in any vertex cover, we have ν ( Γ L ( G s , G t ) ) ≤ τ ( Γ L ( G s , G t ) ) \nu(\Gamma_L(G_s,G_t))\leq\tau(\Gamma_L(G_s,G_t)) ν ( Γ L ( G s , G t )) ≤ τ ( Γ L ( G s , G t )) .
Any maximum matching on a graph with n n n vertices and m m m edges takes O ( m n ) O(m\sqrt{n}) O ( m n ) time [34 ] . Since Γ L ( G s , G t ) \Gamma_L(G_s,G_t) Γ L ( G s , G t ) has at most ∣ V ∣ 2 |V|^2 ∣ V ∣ 2 vertices and one edge per forbidden triple, the forbidden triples can be listed and the matching bound computed in polynomial time. The following proposition summarizes the results, with formal proof in Appendix C.1.
Proposition 2 (Bounds for common lower graphs). For every G s , G t ∈ G G_s,G_t\in\mathcal{G} G s , G t ∈ G , we have
∣ E ( D ∩ ( G s , G t ) ) ∣ ≤ ρ L ( G s , G t ) ≤ ∣ Skel ∩ ( G s , G t ) ∣ − τ ( Γ L ( G s , G t ) ) ≤ ∣ Skel ∩ ( G s , G t ) ∣ − ν ( Γ L ( G s , G t ) ) . |E(\mathcal{D}_{\cap}(G_s,G_t))|\leq\rho_L(G_s,G_t)\leq|\operatorname{Skel}_{\cap}(G_s,G_t)|-\tau(\Gamma_L(G_s,G_t))\leq|\operatorname{Skel}_{\cap}(G_s,G_t)|-\nu(\Gamma_L(G_s,G_t)). ∣ E ( D ∩ ( G s , G t )) ∣ ≤ ρ L ( G s , G t ) ≤ ∣ Skel ∩ ( G s , G t ) ∣ − τ ( Γ L ( G s , G t )) ≤ ∣ Skel ∩ ( G s , G t ) ∣ − ν ( Γ L ( G s , G t )) .
The bounds can sometimes determine the optimal common lower graph without any search. In particular, if ∣ E ( D ∩ ( G s , G t ) ) ∣ = ∣ Skel ∩ ( G s , G t ) ∣ − ν ( Γ L ( G s , G t ) ) |E(D_{\cap}(G_s,G_t))|=|\operatorname{Skel}_{\cap}(G_s,G_t)|-\nu(\Gamma_L(G_s,G_t)) ∣ E ( D ∩ ( G s , G t )) ∣ = ∣ Skel ∩ ( G s , G t ) ∣ − ν ( Γ L ( G s , G t )) , every inequality in Proposition 2 holds with equality. The CPDAG of D ∩ ( G s , G t ) D_{\cap}(G_s,G_t) D ∩ ( G s , G t ) is then a largest-rank common lower graph, so the lower graph can be obtained directly.
5.1.2. Bounds for constructing a common upper graph. For the confidence interval, we also want a common upper graph with rank as small as possible, since a smaller upper endpoint produces a narrower interval. Every common upper graph must contain Skel ∪ ( G s , G t ) \operatorname{Skel}_{\cup}(G_s,G_t) Skel ∪ ( G s , G t ) , giving the immediate lower bound
∣ Skel ∪ ( G s , G t ) ∣ ≤ ρ U ( G s , G t ) . |\operatorname{Skel}_{\cup}(G_s,G_t)|\leq\rho_U(G_s,G_t). ∣ Skel ∪ ( G s , G t ) ∣ ≤ ρ U ( G s , G t ) .
To obtain an upper bound on ρ ( G s , G t ) \rho(G_s,G_t) ρ ( G s , G t ) , we construct a feasible common upper graph. We first take the union of the moral graphs of G s G_s G s and G t G_t G t , where each moral graph is obtained by joining the two endpoints of every v v v -structure. We then add edges until the union is chordal, meaning that every cycle of length at least four has an edge joining two nonconsecutive vertices. This operation is a chordal completion ([42 ] ). We denote the resulting undirected graph by G c h ( G s , G t ) G_{\mathrm{ch}}(G_s,G_t) G ch ( G s , G t ) .
The graph G c h ( G s , G t ) G_{\mathrm{ch}}(G_s,G_t) G ch ( G s , G t ) is a CPDAG and a common upper graph, and therefore
ρ U ( G s , G t ) ≤ rank ( G c h ( G s , G t ) ) . \rho_U(G_s,G_t)\leq\operatorname{rank}(G_{\mathrm{ch}}(G_s,G_t)). ρ U ( G s , G t ) ≤ rank ( G ch ( G s , G t )) .
Any chordal completion gives a valid bound, but completions with fewer added edges give tighter bounds. A minimal completion, in which no added edge can be removed without breaking chordality, can be computed in O ( ∣ V ∣ 3 ) O(|V|^3) O ( ∣ V ∣ 3 ) time ([42 ] ). In contrast, finding a completion with the fewest added edges is NP-hard ([60 ] ). The proof of the following proposition is given in Appendix C.§ 1 .
Proposition 3 (Bounds for common upper graphs). For every G s , G t ∈ G G_s,G_t\in\mathcal{G} G s , G t ∈ G , we have
∣ Skel ∪ ( G s , G t ) ∣ ≤ ρ U ( G s , G t ) ≤ rank ( G c h ( G s , G t ) ) . |\operatorname{Skel}_{\cup}(G_s,G_t)|\leq\rho_U(G_s,G_t)\leq\operatorname{rank}(G_{\mathrm{ch}}(G_s,G_t)). ∣ Skel ∪ ( G s , G t ) ∣ ≤ ρ U ( G s , G t ) ≤ rank ( G ch ( G s , G t )) .
The constructions and Propositions 2 and 3 extend directly to any finite collection A \mathcal{A} A of CPDAGs. We replace pairwise intersections and unions by intersections and unions over all graphs in A \mathcal{A} A . A triple is forbidden for A \mathcal{A} A if both legs appear in every graph, the shield appears in no graph, and the triple is a v v v -structure in some but not all graphs in A \mathcal{A} A .
Exact distances for structured pairs
We show how the model-oriented distance can be computed efficiently when the endpoint graphs G s G_s G s and G t G_t G t have special structure, namely shared disconnected components or polytree skeletons. In § 6.2 , we use these results to obtain upper bounds on the distance for general CPDAGs by projecting them onto these structured classes.
Distance decomposition over disconnected components
When both graphs G s G_s G s and G t G_t G t decompose into the same disconnected components, the distance can be computed separately within each component. For W ⊆ V W\subseteq V W ⊆ V , define G ∣ W \mathcal{G}|_W G ∣ W as the CPDAG corresponding to D [ W ] D[W] D [ W ] , where D [ W ] D[W] D [ W ] is the subgraph induced by W W W in any DAG representative D D D of G \mathcal{G} G . The restriction does not depend on the representative, since all choices have the same induced skeleton and v v v -structures. Let d W d_W d W denote the model-oriented distance between CPDAGs on the vertex set W W W .
Theorem 3 (Decomposition). Let V 1 , … , V K V_1,\ldots,V_K V 1 , … , V K partition V V V so that neither G s G_s G s nor G t G_t G t has an edge between distinct components. Then
d ( G s , G t ) = ∑ k = 1 K d V k ( G s ∣ V k , G t ∣ V k ) , d(\mathcal{G}_s,\mathcal{G}_t)=\sum_{k=1}^{K}d_{V_k}(\mathcal{G}_s|_{V_k},\mathcal{G}_t|_{V_k}), d ( G s , G t ) = k = 1 ∑ K d V k ( G s ∣ V k , G t ∣ V k ) , and no graph on any shortest path has an edge between different components.
We prove this theorem in Appendix C.§ 3 . The theorem shows that when the two endpoint graphs decompose over the same groups, the distance decomposes additively across them. Thus, the full distance problem can be solved separately within each component, potentially leading to substantial computational savings. The connected components of Skel ( G s ) ∪ Skel ( G t ) \operatorname{Skel}(G_s)\cup\operatorname{Skel}(G_t) Skel ( G s ) ∪ Skel ( G t ) give the finest partition satisfying the conditions of the theorem.
Polytrees
We call a CPDAG a polytree when its skeleton has no undirected cycles. For two polytrees, as we establish next, there always exists a shortest path that is both a down-up path and consists only of polytrees. We use d ↓ ↑ ( G s , G t ) d_{\downarrow\uparrow}(G_s,G_t) d ↓↑ ( G s , G t ) from Remark 1.
Theorem 4 (Polytrees). Let G s G_s G s and G t G_t G t be polytrees. Then
d ( G s , G t ) = d ↓ ↑ ( G s , G t ) . d(G_s,G_t)=d_{\downarrow\uparrow}(G_s,G_t). d ( G s , G t ) = d ↓↑ ( G s , G t ) . Moreover, every graph on a down-up path from G s G_s G s to G t G_t G t is a polytree.
We prove this theorem in Appendix C.§ 4 . Taeb et al. [53 ] establish a similar result when the search space is restricted to polytrees. Our theorem removes this restriction: only the two endpoint graphs need to be polytrees, and the minimum is taken over all paths, including paths through arbitrary CPDAGs.
Bounds on the model-oriented distance
In this section, we develop upper and lower bounds on the model-oriented distance d ( G s , G t ) d(G_s,G_t) d ( G s , G t ) .
Upper bounds
A down-up path, defined in Remark 1, can descend from G s G_s G s to a common lower graph G L G_L G L and then ascend to G t G_t G t . Since each step changes rank by one, this path has length rank ( G s ) + rank ( G t ) − 2 rank ( G L ) \operatorname{rank}(G_s)+\operatorname{rank}(G_t)-2\operatorname{rank}(G_L) rank ( G s ) + rank ( G t ) − 2 rank ( G L ) . One can similarly define an up-down path through a common upper graph G U G_U G U . Since both of these are just one set of feasible paths, we have
d ( G s , G t ) ≤ min { rank ( G s ) + rank ( G t ) − 2 rank ( G L ) , 2 rank ( G U ) − rank ( G s ) − rank ( G t ) . d(G_s,G_t)\le\min\left\{
\begin{array}{l}
\operatorname{rank}(G_s)+\operatorname{rank}(G_t)-2\operatorname{rank}(G_L),\\
2\operatorname{rank}(G_U)-\operatorname{rank}(G_s)-\operatorname{rank}(G_t)
\end{array}
\right.. d ( G s , G t ) ≤ min { rank ( G s ) + rank ( G t ) − 2 rank ( G L ) , 2 rank ( G U ) − rank ( G s ) − rank ( G t ) .
Thus, Propositions 2 and 3 give us distance upper bounds without requiring optimal common graphs.
We also construct stronger upper bounds by projecting G s G_s G s and G t G_t G t onto polytree and disconnected component graph classes for which the distance is easier to compute; see § 5.2 . For the polytree projection, we retain a depth-first-search forest of each skeleton, delete the remaining edges from a consistent DAG extension, and convert the result back to the CPDAG. The projected graphs are polytrees, so their distance is given exactly by Theorem 4. For the component projection, we partition the vertex set of the union skeleton into disjoint blocks, delete all edges between blocks from consistent DAG extensions, and convert the results back to CPDAGs. The distance between the projected graphs then decomposes across these blocks and can be computed exactly.
Each projection is obtained from the original graph through a known number of edge deletions. The triangle inequality therefore bounds the original distance by the projected distance plus the deletion counts. We denote the resulting bounds by
u c o m p o n e n t ( G s , G t ) and u p o l y t r e e ( G s , G t ) . u_{\mathrm{component}}(G_s,G_t)\quad\text{and}\quad u_{\mathrm{polytree}}(G_s,G_t). u component ( G s , G t ) and u polytree ( G s , G t ) .
Detour operations
Neighboring CPDAGs have DAG representatives that differ by one edge addition or deletion (Chickering, [6 ] ). Hence, every path must change each pair in Skel ( G s ) △ Skel ( G t ) \operatorname{Skel}(G_s)\mathbin{\triangle}\operatorname{Skel}(G_t) Skel ( G s ) △ Skel ( G t ) at least once. Orientation constraints can force additional temporary changes.
Definition 12 (Detour operations). A step of a path from G s G_s G s to G t G_t G t is a detour if it changes the status of a vertex pair away from its state in the target skeleton. There are two types of detour operations:
E R ( a , b ) : remove { a , b } ∈ Skel ( G t ) , E A ( a , b ) : add { a , b } ∉ Skel ( G t ) . \begin{aligned}
\mathrm{ER}(a,b)&:\quad\text{remove }\{a,b\}\in\operatorname{Skel}(G_t),\\
\mathrm{EA}(a,b)&:\quad\text{add }\{a,b\}\notin\operatorname{Skel}(G_t).
\end{aligned} ER ( a , b ) EA ( a , b ) : remove { a , b } ∈ Skel ( G t ) , : add { a , b } ∈ / Skel ( G t ) . Every detour operation must later be undone. If q ( P ) q(P) q ( P ) counts the detour operations along a path P P P , including repetitions, then
length ( P ) = ∣ Skel ( G s ) △ Skel ( G t ) ∣ + 2 q ( P ) . (6) \operatorname{length}(P)=\left|\operatorname{Skel}(G_s)\mathbin{\triangle}\operatorname{Skel}(G_t)\right|+2q(P). \tag*{(6)} length ( P ) = ∣ Skel ( G s ) △ Skel ( G t ) ∣ + 2 q ( P ) . (6) Thus, every unavoidable detour operation increases the skeleton lower bound by two.
For the collider and chain in Figure 7 (a), any path must delete a leg or add the shield before the collider can change. Each such step is a detour and must later be reversed, so the distance is at least two. Deleting one leg and restoring that leg through a different DAG representative attains this bound.
Figure 7. Two configurations that force detour operations. (a) The skeletons agree, but only the source has the collider a → b ← c a \to b \leftarrow c a → b ← c . Every path must temporarily delete { a , b } \{a,b\} { a , b } or { b , c } \{b,c\} { b , c } , or add { a , c } \{a,c\} { a , c } , and later undo that change. The distance is two. (b) The skeletons differ only in { b , d } \{b,d\} { b , d } . Deleting that edge directly creates a collider absent from the target. The distance is three, attained by deleting { a , b } \{a,b\} { a , b } , deleting { b , d } \{b,d\} { b , d } , and restoring { a , b } \{a,b\} { a , b } through suitable DAG representatives.
More generally, every forbidden triple ( u , w , v ) (u,w,v) ( u , w , v ) (see Definition 10 ) requires at least one operation from
M ( a , b , c ) = { ER ( a , b ) , ER ( b , c ) , EA ( a , c ) } . (7) M_{(a,b,c)}=\{\operatorname{ER}(a,b),\operatorname{ER}(b,c),\operatorname{EA}(a,c)\}. \tag*{(7)} M ( a , b , c ) = { ER ( a , b ) , ER ( b , c ) , EA ( a , c )} . (7)
A single operation may resolve several forbidden triples, so counting them separately can overcount. The bound of Taeb et al. [53 ] accounts for this overlap. We next extend the same idea to conflicts involving more than three vertices.
General mismatches and their lower bound
Forbidden triples do not capture every configuration that forces detour operations. The following example shows a four-node configuration with no forbidden triple, yet the distance is strictly larger than the skeleton difference.
Example 2 (A conflict on four vertices). In Figure 7 (b), the skeletons of G s G_s G s and G t G_t G t differ only in the edge { b , d } \{b,d\} { b , d } . However, deleting { b , d } \{b,d\} { b , d } from G s G_s G s creates the v-structure b → c ← d b \to c \leftarrow d b → c ← d , which is absent from G t G_t G t . Thus, any path must make an additional change before deleting { b , d } \{b,d\} { b , d } , and later undo that change. Hence, d ( G s , G t ) ≥ 3 d(G_s,G_t) \ge3 d ( G s , G t ) ≥ 3 . This bound is attained by deleting from G s G_s G s { a , b } \{a,b\} { a , b } , then { b , d } \{b,d\} { b , d } , and finally restoring { a , b } \{a,b\} { a , b } .
This example motivates the following general notion.
Definition 13 (Mismatch). A mismatch for ( G s , G t ) (G_s,G_t) ( G s , G t ) is a set M M M of detour operations such that every path from G s G_s G s to G t G_t G t must perform at least one operation in M M M .
A forbidden triple is one example of a mismatch. The four-node configuration above gives another. In that example,
{ ER ( a , b ) , ER ( b , c ) , ER ( c , d ) , EA ( a , c ) , EA ( a , d ) , EA ( b , d ) } , \{\operatorname{ER}(a,b),\operatorname{ER}(b,c),\operatorname{ER}(c,d),\operatorname{EA}(a,c),\operatorname{EA}(a,d),\operatorname{EA}(b,d)\}, { ER ( a , b ) , ER ( b , c ) , ER ( c , d ) , EA ( a , c ) , EA ( a , d ) , EA ( b , d )} ,
is a mismatch for ( G s , G t ) (G_s,G_t) ( G s , G t ) .
Now let M \mathcal{M} M be any collection of mismatches. Since every path must hit every M ∈ M M \in\mathcal{M} M ∈ M , its detour operations must form a hitting set for M \mathcal{M} M . Define
m ~ o p ( M ) = min { ∣ H ∣ : H ⊆ ⋃ M ∈ M M , H ∩ M ≠ ∅ for every M ∈ M } . \widetilde{m}_{\mathrm{op}}(\mathcal{M})=\min\left\{|H|:H\subseteq\bigcup_{M\in\mathcal{M}}M,\ H\cap M\ne\varnothing\text{ for every }M\in\mathcal{M}\right\}. m op ( M ) = min { ∣ H ∣ : H ⊆ M ∈ M ⋃ M , H ∩ M = ∅ for every M ∈ M } .
Thus, m ~ o p ( M ) \widetilde{m}_{\mathrm{op}}(\mathcal{M}) m op ( M ) is the minimum number of distinct detour operations needed to hit every mismatch. If one operation resolves several mismatches, it is counted only once.
Theorem 5 (Mismatch lower bound). For every collection M \mathcal{M} M of mismatches for ( G s , G t ) (G_s,G_t) ( G s , G t ) ,
d ( G s , G t ) ≥ ∣ Skel ( G s ) △ Skel ( G t ) ∣ + 2 m ~ o p ( M ) . d(G_s,G_t) \geq|\operatorname{Skel}(G_s)\mathbin{\triangle}\operatorname{Skel}(G_t)| + 2\widetilde{m}_{\mathrm{op}}(\mathcal{M}). d ( G s , G t ) ≥ ∣ Skel ( G s ) △ Skel ( G t ) ∣ + 2 m op ( M ) .
We prove this theorem in Appendix C.§ 2 . The bound follows because every path’s detour operations form a hitting set, and each detour operation must eventually be undone (hence, the factor of two). When M \mathcal{M} M contains only the mismatches induced by forbidden triples, the theorem recovers the bound of Taeb et al. [53 ] . Adding mismatches from larger configurations strengthens the bound, as the four-node example above shows. In Figure 8 , we provide three additional four-node mismatch configurations.
Figure 8. Three additional four-vertex mismatches used by the heuristic h h h . Figure 7 gives the other two mismatches we consider in this paper.
A quickly computable lower bound
Solving the minimum hitting-set problem can be costly. A simpler bound follows by selecting mismatches that share no detour operation. Each selected mismatch must then contribute a distinct detour operation.
To check disjointness, define the support of a mismatch as the set of vertices appearing in its operations. Since every operation acts on a pair of vertices, two mismatches whose supports share at most one vertex cannot share an operation.
Example 3 (Disjoint and overlapping mismatches). Let G s G_s G s be u → w ← v → x ← y u \to w \leftarrow v \to x \leftarrow y u → w ← v → x ← y , and let G t G_t G t be the undirected path u − w − v − x − y u-w-v-x-y u − w − v − x − y . The two skeletons agree. The forbidden triples ( u , w , v ) (u,w,v) ( u , w , v ) and ( v , x , y ) (v,x,y) ( v , x , y ) have supports { u , w , v } \{u,w,v\} { u , w , v } and { v , x , y } \{v,x,y\} { v , x , y } , which share only v v v . Their mismatches are therefore disjoint, so Corollary 2 below gives d ( G s , G t ) ≥ 2 ⋅ 2 = 4 d(G_s,G_t) \geq2 \cdot2 = 4 d ( G s , G t ) ≥ 2 ⋅ 2 = 4 , which is tight. In contrast, consider the four-node example on { a , b , c , d } \{a,b,c,d\} { a , b , c , d } where G s G_s G s has edges a → c a \to c a → c , b → c b \to c b → c and d → c d \to c d → c , and G t G_t G t is the undirected star centered at c c c . The forbidden triples ( a , c , b ) (a,c,b) ( a , c , b ) and ( a , c , d ) (a,c,d) ( a , c , d ) share the pair { a , c } \{a,c\} { a , c } . Hence, both corresponding mismatches contain ER ( a , c ) \operatorname{ER}(a,c) ER ( a , c ) , so they are not disjoint and at most one can be included in a collection I I I of pairwise disjoint mismatches.
Corollary 2 (Disjoint mismatches). Let I I I be a collection of pairwise disjoint mismatches. Then
d ( G s , G t ) ≥ ∣ Skel ( G s ) △ Skel ( G t ) ∣ + 2 ∣ I ∣ . d(G_s,G_t) \geq|\operatorname{Skel}(G_s)\mathbin{\triangle}\operatorname{Skel}(G_t)| + 2|I|. d ( G s , G t ) ≥ ∣ Skel ( G s ) △ Skel ( G t ) ∣ + 2∣ I ∣.
A collection I I I can be built greedily by retaining a mismatch whenever its operations are disjoint from those already selected; the collection need not have maximum size for the bound to hold. Scanning all forbidden triples takes O ( ∣ V ∣ 3 ) O(|V|^3) O ( ∣ V ∣ 3 ) time when selected operations are recorded as the collection grows. Four-vertex configurations may improve the bound at additional computational cost.
Computational strategies
The confidence regions of § 4.3 need two computations on the retained collection G ^ n \widehat{\mathcal{G}}_n G n from perturbed PC. First, we compute distances from the center G ^ 0 , n \widehat{\mathcal{G}}_{0,n} G 0 , n to the retained graphs to obtain the radius r ^ n \widehat{r}_n r n , and construct confidence balls. Second, we find common lower and upper bounds of the retained graphs to construct confidence intervals. We compute both with A* search over the Hasse diagram of L \mathcal{L} L , leveraging the bounds from § 5 as heuristics and feasible solutions.
A unified A* procedure
We perform the required computations using the A* algorithm of Hart et al. [20 ] on the Hasse diagram of L \mathcal{L} L . Unlike breadth-first search, A* prioritizes states using lower bounds on the remaining search cost, allowing shortest paths or extremal feasible elements to be found efficiently. In our setting, the search graph is the undirected Hasse diagram of L \mathcal{L} L , whose edges are covering relations of unit length. Thus, shortest path search yields the model-oriented distance needed for the confidence ball, while constrained searches over the same poset yield common lower and upper graphs needed for the confidence interval.
We use a common A* framework for these tasks. Each search is specified by the following ingredients:
G s G_s G s : initial graph where the search begins;
S ( G ) S(G) S ( G ) : the neighboring CPDAGs that the search may visit from G G G ;
T ( G ) ∈ { 0 , 1 } T(G) \in\{0,1\} T ( G ) ∈ { 0 , 1 } : T ( G ) = 1 T(G)=1 T ( G ) = 1 if G G G is a terminal state;
h ( G ) h(G) h ( G ) : a lower bound, called a heuristic, on the remaining distance from G G G to a terminal state;
Algorithm 3: Unified A* search over the CPDAG poset
Input: Initial graph G s \mathcal{G}_s G s ; successor operator S S S ; terminal condition T T T ; heuristic h h h ; completion C C C ; initial upper bound U 0 U_0 U 0 (default ∞ \infty ∞ )
Output: Best terminal graph and path length, with optimality flag
( G b e s t , ℓ ) ← C ( G s ) (\mathcal{G}_{\mathrm{best}}, \ell) \leftarrow C(\mathcal{G}_s) ( G best , ℓ ) ← C ( G s ) ; U ← min { ℓ , U 0 } U \leftarrow\min\{\ell, U_0\} U ← min { ℓ , U 0 } ;
g ( G s ) ← 0 g(\mathcal{G}_s) \leftarrow0 g ( G s ) ← 0 ; f ( G s ) ← h ( G s ) f(\mathcal{G}_s) \leftarrow h(\mathcal{G}_s) f ( G s ) ← h ( G s ) ;
O P E N ← { G s } \mathrm{OPEN} \leftarrow\{\mathcal{G}_s\} OPEN ← { G s } , ordered by ( f , − g ) (f, -g) ( f , − g ) ;
while OPEN ≠ ∅ \ne\emptyset = ∅ and time remains do
G ← O P E N . p o p m i n ( ) \mathcal{G} \leftarrow\mathrm{OPEN.popmin}() G ← OPEN.popmin ( ) ;
if f ( G ) ≥ U f(\mathcal{G}) \ge U f ( G ) ≥ U then
return G b e s t , U , o p t i m a l \mathcal{G}_{\mathrm{best}}, U, \mathit{optimal} G best , U , optimal ;
if T ( G ) T(\mathcal{G}) T ( G ) then
G b e s t ← G \mathcal{G}_{\mathrm{best}} \leftarrow\mathcal{G} G best ← G ; U ← g ( G ) U \leftarrow g(\mathcal{G}) U ← g ( G ) ;
return G b e s t , U , o p t i m a l \mathcal{G}_{\mathrm{best}}, U, \mathit{optimal} G best , U , optimal ;
foreach G ′ ∈ S ( G ) \mathcal{G}' \in S(\mathcal{G}) G ′ ∈ S ( G ) , subject to pruning restrictions do
g ′ ← g ( G ) + 1 g' \leftarrow g(\mathcal{G}) + 1 g ′ ← g ( G ) + 1 ;
if G ′ \mathcal{G}' G ′ is unseen or g ′ < g ( G ′ ) g' < g(\mathcal{G}') g ′ < g ( G ′ ) then
g ( G ′ ) ← g ′ g(\mathcal{G}') \leftarrow g' g ( G ′ ) ← g ′ ;
( G c , ℓ ) ← C ( G ′ ) (\mathcal{G}_c,\ell) \leftarrow C(\mathcal{G}') ( G c , ℓ ) ← C ( G ′ ) ;
if g ′ + ℓ < U g' + \ell< U g ′ + ℓ < U then
G b e s t ← G c \mathcal{G}_{\mathrm{best}} \leftarrow\mathcal{G}_c G best ← G c ;
U ← g ′ + ℓ U \leftarrow g' + \ell U ← g ′ + ℓ ;
f ( G ′ ) ← g ′ + h ( G ′ ) f(\mathcal{G}') \leftarrow g' + h(\mathcal{G}') f ( G ′ ) ← g ′ + h ( G ′ ) ;
if f ( G ′ ) < U f(\mathcal{G}') < U f ( G ′ ) < U then
O P E N ← O P E N ∪ { G ′ } \mathrm{OPEN} \leftarrow\mathrm{OPEN} \cup\{\mathcal{G}'\} OPEN ← OPEN ∪ { G ′ } ;
if OPEN = ∅ = \emptyset = ∅ then
return G b e s t , U , o p t i m a l \mathcal{G}_{\mathrm{best}}, U, \mathit{optimal} G best , U , optimal ;
return G b e s t , U , n o t c e r t i f i e d o p t i m a l \mathcal{G}_{\mathrm{best}}, U, \mathit{not\ certified\ optimal} G best , U , not certified optimal ;
C ( G ) C(\mathcal{G}) C ( G ) : a tuple consisting of a feasible terminal state together with the length of a path from G \mathcal{G} G to that state;
U 0 U_0 U 0 : initial upper bound for the distance from G s \mathcal{G}_s G s to a terminal state.
A* also keeps g ( G ) g(\mathcal{G}) g ( G ) , the length of the shortest path from G s \mathcal{G}_s G s to G \mathcal{G} G found so far, and expands states in increasing order of
f ( G ) : = g ( G ) + h ( G ) . f(\mathcal{G}) := g(\mathcal{G}) + h(\mathcal{G}). f ( G ) := g ( G ) + h ( G ) .
The completion C ( G ) C(\mathcal{G}) C ( G ) provides an upper bound on the shortest feasible path length from the start to a terminal state, so states that cannot improve the current best solution can be pruned. Once the smallest remaining f f f -value reaches the current upper bound, the best solution is certified optimal. Note that constrained searches use the same algorithm, with S S S and T T T restricted to the admissible portion of the Hasse diagram.
Algorithm 3 summarizes the unified search. It returns the best feasible terminal state found and certifies optimality whenever the A* lower bound meets the current upper bound. If terminated early, it returns the best feasible solution without certification. Using the returned path lengths as distance upper bounds for the ball, or the returned common graphs as feasible interval endpoints, yields conservative regions and therefore preserves the coverage guarantee.
Computing the confidence ball
To construct the confidence ball, we need the model-oriented distance from the center G ^ 0 , n \widehat{\mathcal{G}}_{0,n} G 0 , n to each graph in G ~ n \widetilde{\mathcal{G}}_n G n . We therefore solve the same shortest path problem repeatedly, taking G s = G ^ 0 , n \mathcal{G}_s = \widehat{\mathcal{G}}_{0,n} G s = G 0 , n as the start graph and G t ∈ G ~ n \mathcal{G}_t \in\widetilde{\mathcal{G}}_n G t ∈ G n as the target.
For a generic pair ( G s , G t ) (\mathcal{G}_s,\mathcal{G}_t) ( G s , G t ) , let N ( G ) \mathcal{N}(\mathcal{G}) N ( G ) be the neighbors of graph G \mathcal{G} G in the CPDAG Hasse diagram, i.e., the CPDAGs that either are covered by G \mathcal{G} G or cover G \mathcal{G} G . To compute the distance from G s \mathcal{G}_s G s to G t \mathcal{G}_t G t , the search starts at G s \mathcal{G}_s G s , and uses
S D ( G ) = N ( G ) , T D ( G ) = 1 { G = G t } . S_D(\mathcal{G})=\mathcal{N}(\mathcal{G}), \qquad T_D(\mathcal{G})=\mathbf{1}\{\mathcal{G}=\mathcal{G}_t\}. S D ( G ) = N ( G ) , T D ( G ) = 1 { G = G t } .
Thus, the search may move along any covering relation and terminate when it reaches G t \mathcal{G}_t G t .
Computing the heuristic h h h
In order to certify optimality of A*, the heuristic must be admissible , meaning h ( G ) h(\mathcal{G}) h ( G ) lower bounds the shortest path length from G \mathcal{G} G to a terminal state [20 ] . By Theorem 5, every collection of mismatches for ( G , G t ) (\mathcal{G},\mathcal{G}_t) ( G , G t ) gives an admissible heuristic. A heuristic is also consistent if h ( G ) = 0 h(\mathcal{G})=0 h ( G ) = 0 at terminal states and h ( G ) ≤ 1 + h ( G ′ ) h(\mathcal{G})\leq1+h(\mathcal{G}') h ( G ) ≤ 1 + h ( G ′ ) for every G ′ ∈ S D ( G ) \mathcal{G}'\in S_D(\mathcal{G}) G ′ ∈ S D ( G ) . With a consistent heuristic, no state is reopened, so each state is expanded at most once, improving the efficiency of the search. We next establish consistency for the collection of all mismatches and for the collection of all forbidden-triple mismatches.
Proposition 4 (Consistency). Fix a target G t \mathcal{G}_t G t . For every G \mathcal{G} G , let M ( G , G t ) \mathcal{M}(\mathcal{G},\mathcal{G}_t) M ( G , G t ) be the collection of all mismatches for ( G , G t ) (\mathcal{G},\mathcal{G}_t) ( G , G t ) . Then the heuristic
h ( G ) = ∣ Skel ( G ) △ Skel ( G t ) ∣ + 2 m ~ o p ( M ( G , G t ) ) h(\mathcal{G})=\lvert\operatorname{Skel}(\mathcal{G})\mathbin{\triangle}\operatorname{Skel}(\mathcal{G}_t)\rvert+2\widetilde{m}_{\mathrm{op}}(\mathcal{M}(\mathcal{G},\mathcal{G}_t)) h ( G ) = ∣ Skel ( G ) △ Skel ( G t )∣ + 2 m op ( M ( G , G t )) is consistent for the distance search. The same conclusion holds when M ( G , G t ) \mathcal{M}(\mathcal{G},\mathcal{G}_t) M ( G , G t ) is the collection of all forbidden-triple mismatches for every G \mathcal{G} G . In particular, the bound of Taeb et al. [53 ] is consistent.
We prove both cases of Proposition 4 in Appendix D.1.
Computing h h h requires solving a minimum hitting-set problem, which is impractical for a high number of nodes. In practice, we use the polynomial-time bound of Corollary 2. For the current state-target pair ( G , G t ) (\mathcal{G},\mathcal{G}_t) ( G , G t ) , we detect the mismatch patterns listed below and form their mismatch-conflict graph , which has one vertex per detected mismatch and joins two mismatches when they share an operation. An independent set of this graph is a collection of pairwise disjoint mismatches. We construct such a set I ( G , G t ) I(\mathcal{G},\mathcal{G}_t) I ( G , G t ) greedily, by repeatedly selecting a vertex of minimum degree and deleting it and its neighbors. We then set
h D ( G ) = ∣ Skel ( G ) △ Skel ( G t ) ∣ + 2 ∣ I ( G , G t ) ∣ . h_D(\mathcal{G})=\lvert\operatorname{Skel}(\mathcal{G})\mathbin{\triangle}\operatorname{Skel}(\mathcal{G}_t)\rvert+2\lvert I(\mathcal{G},\mathcal{G}_t)\rvert. h D ( G ) = ∣ Skel ( G ) △ Skel ( G t )∣ + 2 ∣ I ( G , G t )∣ .
Each detected pattern gives a mismatch (Appendix D.2), so by Corollary 2, h D h_D h D is a lower bound on d ( G , G t ) d(\mathcal{G},\mathcal{G}_t) d ( G , G t ) . Unlike h h h , the heuristic h D h_D h D need not be consistent. Since h D h_D h D is admissible, the search remains exact, at the cost of occasionally reopening a state.
For the mismatch patterns, we consider the two mismatch types in Figure 7 , as well as the three in Figure 8 . For the four-vertex mismatches, we consider all node relabelings of the patterns. Their corresponding mismatches are:
M 1 = { ER ( a , b ) , ER ( b , c ) , EA ( a , c ) } , M 2 = { ER ( a , b ) , ER ( b , c ) , ER ( c , d ) , EA ( a , c ) , EA ( a , d ) , EA ( b , d ) } , M 3 = { ER ( a , b ) , ER ( a , c ) , ER ( b , c ) , ER ( c , d ) , EA ( b , d ) , EA ( a , d ) } , M 4 = { ER ( a , b ) , ER ( b , c ) , ER ( c , d ) , EA ( a , d ) , EA ( b , d ) , EA ( a , c ) } , M 5 = { ER ( a , b ) , ER ( b , c ) , ER ( c , d ) , ER ( a , d ) , EA ( a , c ) , EA ( b , d ) } . \begin{aligned}
M_1 &= \{\operatorname{ER}(a,b),\operatorname{ER}(b,c),\operatorname{EA}(a,c)\},\\
M_2 &= \{\operatorname{ER}(a,b),\operatorname{ER}(b,c),\operatorname{ER}(c,d),\operatorname{EA}(a,c),\operatorname{EA}(a,d),\operatorname{EA}(b,d)\},\\
M_3 &= \{\operatorname{ER}(a,b),\operatorname{ER}(a,c),\operatorname{ER}(b,c),\operatorname{ER}(c,d),\operatorname{EA}(b,d),\operatorname{EA}(a,d)\},\\
M_4 &= \{\operatorname{ER}(a,b),\operatorname{ER}(b,c),\operatorname{ER}(c,d),\operatorname{EA}(a,d),\operatorname{EA}(b,d),\operatorname{EA}(a,c)\},\\
M_5 &= \{\operatorname{ER}(a,b),\operatorname{ER}(b,c),\operatorname{ER}(c,d),\operatorname{ER}(a,d),\operatorname{EA}(a,c),\operatorname{EA}(b,d)\}.
\end{aligned} M 1 M 2 M 3 M 4 M 5 = { ER ( a , b ) , ER ( b , c ) , EA ( a , c )} , = { ER ( a , b ) , ER ( b , c ) , ER ( c , d ) , EA ( a , c ) , EA ( a , d ) , EA ( b , d )} , = { ER ( a , b ) , ER ( a , c ) , ER ( b , c ) , ER ( c , d ) , EA ( b , d ) , EA ( a , d )} , = { ER ( a , b ) , ER ( b , c ) , ER ( c , d ) , EA ( a , d ) , EA ( b , d ) , EA ( a , c )} , = { ER ( a , b ) , ER ( b , c ) , ER ( c , d ) , ER ( a , d ) , EA ( a , c ) , EA ( b , d )} .
Here, M 1 M_1 M 1 is the mismatch of Figure 7 (a) and M 2 M_2 M 2 is the mismatch of Figure 7 (b). The mismatches M 3 M_3 M 3 , M 4 M_4 M 4 and M 5 M_5 M 5 correspond to Figure 8 (a), (b) and (c).
Computing feasible completions
We use several feasible paths to obtain upper bounds on d ( G s , G t ) d(\mathcal{G}_s,\mathcal{G}_t) d ( G s , G t ) . Here, a feasible completion from a current state G \mathcal{G} G is any valid path in the CPDAG Hasse diagram from G \mathcal{G} G to the target G t \mathcal{G}_t G t .
The first feasible path comes from common lower and upper bounds: any common lower graph yields a down-up path, and any common upper graph yields an up-down path; see Remark 1 for the definition of these path types. The shortest such paths have lengths
u ↓ ↑ ( G , G t ) : = rank ( G ) + rank ( G t ) − 2 ρ L ( G , G t ) , u ↑ ↓ ( G , G t ) : = 2 ρ U ( G , G t ) − rank ( G ) − rank ( G t ) , u_{\downarrow\uparrow}(\mathcal{G},\mathcal{G}_t):=\operatorname{rank}(\mathcal{G})+\operatorname{rank}(\mathcal{G}_t)-2\rho_L(\mathcal{G},\mathcal{G}_t), \qquad
u_{\uparrow\downarrow}(\mathcal{G},\mathcal{G}_t):=2\rho_U(\mathcal{G},\mathcal{G}_t)-\operatorname{rank}(\mathcal{G})-\operatorname{rank}(\mathcal{G}_t), u ↓↑ ( G , G t ) := rank ( G ) + rank ( G t ) − 2 ρ L ( G , G t ) , u ↑↓ ( G , G t ) := 2 ρ U ( G , G t ) − rank ( G ) − rank ( G t ) ,
with ρ L \rho_L ρ L and ρ U \rho_U ρ U as in § 5.1 . Computing ρ L \rho_L ρ L and ρ U \rho_U ρ U requires a search. Propositions 2 and 3 instead give the inexpensive polynomial-time upper bounds
u ^ ↓ ↑ ( G , G t ) : = rank ( G ) + rank ( G t ) − 2 ∣ E ( D ∩ ( G , G t ) ) ∣ , \widehat{u}_{\downarrow\uparrow}(G,G_t) := \operatorname{rank}(G) + \operatorname{rank}(G_t) - 2\lvert E(\mathcal{D}_{\cap}(G,G_t))\rvert, u ↓↑ ( G , G t ) := rank ( G ) + rank ( G t ) − 2 ∣ E ( D ∩ ( G , G t ))∣ ,
u ^ ↑ ↓ ( G , G t ) : = 2 rank ( G c h ( G , G t ) ) − rank ( G ) − rank ( G t ) . \widehat{u}_{\uparrow\downarrow}(G,G_t) := 2\operatorname{rank}(G_{\mathrm{ch}}(G,G_t)) - \operatorname{rank}(G) - \operatorname{rank}(G_t). u ↑↓ ( G , G t ) := 2 rank ( G ch ( G , G t )) − rank ( G ) − rank ( G t ) .
We then use the completion
C D ( G ) = ( G t , min { u ^ ↓ ↑ ( G , G t ) , u ^ ↑ ↓ ( G , G t ) } ) . C_D(G) = \left(G_t,\min\left\{\widehat{u}_{\downarrow\uparrow}(G,G_t),\widehat{u}_{\uparrow\downarrow}(G,G_t)\right\}\right). C D ( G ) = ( G t , min { u ↓↑ ( G , G t ) , u ↑↓ ( G , G t ) } ) .
We set the initial upper bound U 0 U_0 U 0 as
U 0 = min { u c o m p o n e n t ( G s , G t ) , u p o l y t r e e ( G s , G t ) , u ↓ ↑ ( G s , G t ) , u ↑ ↓ ( G s , G t ) } . U_0 = \min\left\{u_{\mathrm{component}}(G_s,G_t),u_{\mathrm{polytree}}(G_s,G_t),u_{\downarrow\uparrow}(G_s,G_t),u_{\uparrow\downarrow}(G_s,G_t)\right\}. U 0 = min { u component ( G s , G t ) , u polytree ( G s , G t ) , u ↓↑ ( G s , G t ) , u ↑↓ ( G s , G t ) } .
where u c o m p o n e n t ( G s , G t ) u_{\mathrm{component}}(G_s,G_t) u component ( G s , G t ) and u p o l y t r e e ( G s , G t ) u_{\mathrm{polytree}}(G_s,G_t) u polytree ( G s , G t ) are described in § 5.3.1 . Note that during the search, for any intermediate graph G G G , we update the upper bound using the cheaper polynomial-time upper bounds on u ↓ ↑ ( G , G t ) u_{\downarrow\uparrow}(G,G_t) u ↓↑ ( G , G t ) and u ↑ ↓ ( G , G t ) u_{\uparrow\downarrow}(G,G_t) u ↑↓ ( G , G t ) .
Pruning strategies
We further reduce the search by excluding covering operations to graphs that cannot occur on a shortest path. First, let G L G_L G L and G U G_U G U be any common lower and upper graphs of G s G_s G s and G t G_t G t , respectively. Every graph G G G on a shortest path satisfies
rank ( G L ) ≤ rank ( G ) ≤ rank ( G U ) . \operatorname{rank}(G_L) \le\operatorname{rank}(G) \le\operatorname{rank}(G_U). rank ( G L ) ≤ rank ( G ) ≤ rank ( G U ) .
Indeed, a path that visits a graph of rank below rank ( G L ) \operatorname{rank}(G_L) rank ( G L ) or above rank ( G U ) \operatorname{rank}(G_U) rank ( G U ) is longer than the corresponding down-up or up-down path. We therefore generate only neighbors within this rank interval. Tighter common bounds give stronger pruning, although the polynomial-time constructions of Propositions 2 and 3 already provide valid bounds.
Second, shortest paths never introduce edges that are disjoint from all differences between the start and target graphs. Let V Δ V_{\Delta} V Δ be the set of vertices that are endpoints of a pair in Skel ( G s ) △ Skel ( G t ) \operatorname{Skel}(G_s)\mathbin{\triangle}\operatorname{Skel}(G_t) Skel ( G s ) △ Skel ( G t ) or belong to a triple that is a v v v -structure in exactly one of the two graphs. A disjoint stray edge is an edge absent from both skeletons whose endpoints both lie outside V Δ V_{\Delta} V Δ .
Proposition 5 (Disjoint stray edges). No graph on a shortest path from G s G_s G s to G t G_t G t contains a disjoint stray edge.
See Appendix D.§ 3 for a proof. We therefore exclude such edge additions when generating neighbors.
Computing the confidence interval
The goal is to construct a common lower graph and a common upper graph for all CPDAGs in G ^ n \widehat{\mathcal{G}}_n G n , which determine the endpoints of the confidence interval. We do this sequentially: starting from two CPDAGs, we compute a common lower and upper graph, then combine each resulting graph with the next CPDAG in the collection, and continue until all graphs have been incorporated. As described next, each common-bound problem is solved using our A* framework.
For a pair ( G 1 , G 2 ) (\mathcal{G}_1, \mathcal{G}_2) ( G 1 , G 2 ) , the common-lower search starts from the graph of smaller rank, say G 1 \mathcal{G}_1 G 1 , and moves only downward in the Hasse diagram. Thus, S L ( G ) S_L(\mathcal{G}) S L ( G ) consists of CPDAGs covered by G \mathcal{G} G , and a state G \mathcal{G} G is terminal if it is a lower bound of both graphs:
S L ( G ) = { G ′ ∈ G : G covers G ′ } and T L ( G ) : = 1 { G ⪯ G 1 and G ⪯ G 2 } . S_L(\mathcal{G}) = \{\mathcal{G}' \in\mathbb{G} : \mathcal{G} \text{ covers } \mathcal{G}'\}
\quad\text{and}\quad
T_L(\mathcal{G}) := \mathbf{1}\{\mathcal{G} \preceq\mathcal{G}_1 \text{ and } \mathcal{G} \preceq\mathcal{G}_2\}. S L ( G ) = { G ′ ∈ G : G covers G ′ } and T L ( G ) := 1 { G ⪯ G 1 and G ⪯ G 2 } .
Because each downward move decreases rank by one, the shortest terminal path ends at a common lower bound of the largest rank. At an intermediate state G \mathcal{G} G , any terminal state reachable from G \mathcal{G} G must be a common lower bound of G , G 2 \mathcal{G}, \mathcal{G}_2 G , G 2 . Proposition 2 provides both the heuristic h L ( G ) h_L(\mathcal{G}) h L ( G ) and a feasible completion C L ( G ) C_L(\mathcal{G}) C L ( G ) . Let G ∩ ( G , G 2 ) \mathcal{G}_{\cap}(\mathcal{G}, \mathcal{G}_2) G ∩ ( G , G 2 ) denote the CPDAG of D ∩ ( G , G 2 ) \mathcal{D}_{\cap}(\mathcal{G}, \mathcal{G}_2) D ∩ ( G , G 2 ) :
h L ( G ) = rank ( G ) − ( ∣ Skel ∩ ( G , G 2 ) ∣ − ν ( Γ L ( G , G 2 ) ) ) , h_L(\mathcal{G}) = \operatorname{rank}(\mathcal{G}) - \left(\lvert\operatorname{Skel}_{\cap}(\mathcal{G}, \mathcal{G}_2)\rvert- \nu(\Gamma_L(\mathcal{G}, \mathcal{G}_2))\right), h L ( G ) = rank ( G ) − ( ∣ Skel ∩ ( G , G 2 )∣ − ν ( Γ L ( G , G 2 )) ) ,
C L ( G ) = ( G ∩ ( G , G 2 ) , rank ( G ) − ∣ E ( D ∩ ( G , G 2 ) ) ∣ ) . C_L(\mathcal{G}) = \left(\mathcal{G}_{\cap}(\mathcal{G}, \mathcal{G}_2), \operatorname{rank}(\mathcal{G}) - \lvert E(\mathcal{D}_{\cap}(\mathcal{G}, \mathcal{G}_2))\rvert\right). C L ( G ) = ( G ∩ ( G , G 2 ) , rank ( G ) − ∣ E ( D ∩ ( G , G 2 ))∣ ) .
The common-upper search is symmetric. We relabel the pair so that rank ( G 1 ) ≥ rank ( G 2 ) \operatorname{rank}(\mathcal{G}_1) \ge\operatorname{rank}(\mathcal{G}_2) rank ( G 1 ) ≥ rank ( G 2 ) . The search starts from G 1 \mathcal{G}_1 G 1 and moves only upward:
S U ( G ) = { G ′ ∈ G : G ′ covers G } , T U ( G ) = 1 { G 1 ⪯ G and G 2 ⪯ G } . S_U(\mathcal{G}) = \{\mathcal{G}' \in\mathbb{G} : \mathcal{G}' \text{ covers } \mathcal{G}\},
\quad
T_U(\mathcal{G}) = \mathbf{1}\{\mathcal{G}_1 \preceq\mathcal{G} \text{ and } \mathcal{G}_2 \preceq\mathcal{G}\}. S U ( G ) = { G ′ ∈ G : G ′ covers G } , T U ( G ) = 1 { G 1 ⪯ G and G 2 ⪯ G } .
The shortest terminal path therefore ends at a common upper graph of smallest rank. At a state G \mathcal{G} G , every terminal state is a common upper graph of G \mathcal{G} G and G 2 \mathcal{G}_2 G 2 . Proposition 3 applied to ( G , G 2 ) (\mathcal{G}, \mathcal{G}_2) ( G , G 2 ) gives the heuristic and the completion:
h U ( G ) = ∣ Skel ∪ ( G , G 2 ) ∣ − rank ( G ) , h_U(\mathcal{G}) = \lvert\operatorname{Skel}_{\cup}(\mathcal{G}, \mathcal{G}_2)\rvert- \operatorname{rank}(\mathcal{G}), h U ( G ) = ∣ Skel ∪ ( G , G 2 )∣ − rank ( G ) ,
C U ( G ) = ( G ch ( G , G 2 ) , rank ( G ch ( G , G 2 ) ) − rank ( G ) ) . C_U(\mathcal{G}) = \left(\mathcal{G}_{\operatorname{ch}}(\mathcal{G}, \mathcal{G}_2), \operatorname{rank}(\mathcal{G}_{\operatorname{ch}}(\mathcal{G}, \mathcal{G}_2)) - \operatorname{rank}(\mathcal{G})\right). C U ( G ) = ( G ch ( G , G 2 ) , rank ( G ch ( G , G 2 )) − rank ( G ) ) .
Simulations on confidence regions
In this section, we evaluate the confidence regions constructed by Algorithm 2 and assess their coverage and how their radius or width changes with sample size, signal strength, and graph structure. As benchmarks, we compare against the perturbed PC collection of Chang et al. [4 ] and the standard PC point estimate. All comparisons use the same population models, datasets, resamples, and random seeds.
Unless otherwise noted, confidence balls and intervals are constructed from the collection returned by Algorithm 1 using its default parameters. We also consider parameter choices in Algorithm 1 that reproduce the perturbed PC collection of Chang et al. [4 ] .
Setup
For a given DAG, we generate data from a linear Gaussian structural equation model (SEM):
X j = ∑ k ∈ Pa ( j ) β k j X k + ε j , ε j ∼ i n d N ( 0 , 1 ) . X_j = \sum_{k \in\operatorname{Pa}(j)} \beta_{kj}X_k + \varepsilon_j,\qquad\varepsilon_j \mathrel{\overset{\mathrm{ind}}{\sim}} \mathcal{N}(0,1). X j = k ∈ Pa ( j ) ∑ β k j X k + ε j , ε j ∼ ind N ( 0 , 1 ) .
To sample a DAG, we first draw a uniformly random ordering of the p p p vertices. Each pair of vertices is then connected independently with the edge probability of the regime (Table 1 ), with the edge directed from the earlier to the later vertex in the sampled ordering. Edge coefficients β k j \beta_{kj} β k j are drawn uniformly from [ 2 , 3 ] [2,3] [ 2 , 3 ] .
Table 1. Simulation regimes for the confidence region experiments. The three non-temporal sparse regimes range from weak to strong signals as measured through the minimum nonzero partial correlation coefficient.
For regimes with temporal information, we instead sample a topological ordering consistent with the prescribed tiers: vertices are randomly ordered within each tier, while all vertices in an earlier tier precede those in a later tier. Edges are then sampled and oriented according to this ordering in the same way. Thus, no edge can point from a later tier to an earlier tier, while orientations within a tier remain unrestricted by the temporal information.
We consider five regimes, summarized in Table 1 . The three sparse p = 10 p = 10 p = 10 regimes differ only in the minimum nonzero partial correlation. We obtain each regime by rejection sampling until the minimum nonzero partial correlation falls in the target interval. We also consider two regimes with temporal background information, which assign variables to ordered tiers and forbid edges from later to earlier tiers. Following Chang et al. [4 ] , the dense p = 10 p = 10 p = 10 regime uses the tier assignment O ( V ) = ( 1 , 1 , 1 , 2 , 2 , 2 , 2 , 2 , 3 , 3 ) O(V) = (1,1,1,2,2,2,2,2,3,3) O ( V ) = ( 1 , 1 , 1 , 2 , 2 , 2 , 2 , 2 , 3 , 3 ) (Appendix § 11 .§ 2 ), while the sparse p = 15 p = 15 p = 15 regime uses three tiers of five variables.
For each regime, we sample 20 population SEMs, each consisting of a DAG and its edge coefficients. For each population model and sample size
n ∈ { 100 , 500 , 1000 , 10000 , 30000 } , n \in\{100, 500, 1000, 10000, 30000\}, n ∈ { 100 , 500 , 1000 , 10000 , 30000 } ,
we generate 30 independent datasets. We fix the number of perturbed PC resamples at M = 1000 M = 1000 M = 1000 and use a nominal confidence level 1 − ν = 0.95 1 - \nu= 0.95 1 − ν = 0.95 . Each distance search and each common lower or upper graph search has a time limit of 0.5 seconds. If the timeout is reached, we use the best feasible solution found, which preserves coverage guarantees.
Following Chang et al. [4 ] , their perturbed PC procedure uses the threshold
t c h a n g = c ∗ ( log n M ) 1 / L z ν / ( 2 L ) . t_{\mathrm{chang}} = c^{*}\left(\frac{\log n}{M}\right)^{1/L} z_{\nu/(2L)}. t chang = c ∗ ( M log n ) 1/ L z ν / ( 2 L ) .
Here, in place of L = ∣ T ∣ L = |\mathcal{T}| L = ∣ T ∣ , we use L = ( p 2 ) ( d max + 1 ) L = \binom{p}{2}(d_{\max}+1) L = ( 2 p ) ( d m a x + 1 ) , where d max d_{\max} d m a x is the expected degree of each node. Furthermore, z q = Φ − 1 ( 1 − q ) z_q = \Phi^{-1}(1-q) z q = Φ − 1 ( 1 − q ) denotes the upper-tail Gaussian quantile. The quantity c ∗ c^{*} c ∗ is a tuning parameter. As recommended by Chang et al. [4 ] , we choose this parameter to be small while controlling the number of retained CPDAGs. Our proposed threshold (see § 4.2.4 ) is
t o u r s = 2 log M B , B ∈ { 3 , 6 , 12 , 24 } . t_{\mathrm{ours}} = \sqrt{\frac{2\log M}{B}}, \qquad B \in\{3, 6, 12, 24\}. t ours = B 2 log M , B ∈ { 3 , 6 , 12 , 24 } .
For each population model, B B B is selected once using a dataset of size 10000 from one Monte Carlo run. We split this dataset into 7500 training observations and 2500 holdout observations. For each candidate B B B , we generate M = 10000 M = 10000 M = 10000 perturbed PC runs using the training data and retain the distinct valid CPDAGs. For each retained CPDAG, we choose a consistent DAG extension, fit the corresponding Gaussian DAG model on the training data, and evaluate its average log-likelihood on the holdout data. We then select the smallest B B B whose best holdout score is within 1% of the best score across candidates. The selected B B B is held fixed across all evaluation sample sizes and Monte Carlo trials for that population model.
Results
We evaluate both confidence balls and model confidence intervals on the dense temporal p = 10 p = 10 p = 10 and sparse temporal p = 15 p = 15 p = 15 regimes in Table 1 . Appendix E.§ 1 presents the results for the three sparse non-temporal p = 10 p = 10 p = 10 regimes (rows 2–4 of Table 1 ). For each dataset, we compare the PC point estimate, the perturbed PC collection of Chang et al. [4 ] , and confidence regions constructed from perturbed PC collections. We construct both balls and interval results from the Chang et al. [4 ] collection and from the collection obtained using our proposed threshold t o u r s t_{\mathrm{ours}} t ours . Coverage is the fraction of datasets whose region contains the true CPDAG. Region size is the radius for confidence balls and the width for model confidence intervals. The width is the rank difference between the upper and lower endpoints and is at most p ( p − 1 ) / 2 p(p-1)/2 p ( p − 1 ) /2 , which equals 45 for p = 10 p = 10 p = 10 and 105 for p = 15 p = 15 p = 15 .
Consider first the dense temporal p = 10 p = 10 p = 10 setting. Figure 9 and Figure 10 show the ball and interval results, respectively. The PC point estimate has poor coverage, as expected when structural uncertainty is ignored. The perturbed PC collection of Chang et al. [4 ] can also miscover; although this could be due to the choice of its tuning parameter, which we discuss later. Converting this collection into either a confidence ball or a model confidence interval substantially improves coverage. The proposed threshold maintains comparable coverage while producing substantially more compact regions, with smaller ball radii and narrower intervals.
Figure 9. Confidence ball results for the dense temporal p = 10 p = 10 p = 10 regime. Left: empirical coverage over 600 instances at each n n n . Right: mean radius over the same instances.
Figure 10. Confidence interval results for the dense temporal p = 10 p = 10 p = 10 regime. Left: empirical coverage over 600 instances at each n n n . Right: mean interval width over the same instances.
Consider next the sparse temporal p = 15 p = 15 p = 15 setting. In this setting, the recommended strategy of Chang et al. [4 ] for choosing c ∗ c^* c ∗ leads to poor coverage. We therefore also report an oracle choice of c ∗ c^* c ∗ that maximizes coverage for the perturbed PC collection, providing a more favorable benchmark. We then compare confidence balls and model confidence intervals constructed from this oracle-tuned collection with those obtained using our proposed threshold. Figure 11 and Figure 12 show the ball and interval results, respectively. The oracle choice substantially improves coverage of the perturbed PC collection and also reduces the resulting ball radius and interval width. Even under this favorable tuning, however, the confidence regions remain substantially larger than those obtained using our proposed threshold. Our threshold achieves comparable coverage with markedly smaller radii and narrower intervals.
Figure 11. Confidence ball results for the sparse temporal p = 15 p = 15 p = 15 regime. Left: empirical coverage over 600 instances at each n n n . Right: mean radius over the same instances. For Chang et al. [4 ] , we report results under both their recommended tuning strategy and an oracle choice of c ∗ c^* c ∗ that maximizes coverage.
Figure 12. Confidence interval results for the sparse temporal p = 15 p = 15 p = 15 regime. Left: empirical coverage over 600 instances at each n n n . Right: mean interval width over the same instances. For Chang et al. [4 ] , we report results under both their recommended tuning strategy and an oracle choice of c ∗ c^* c ∗ that maximizes coverage.
The gain in compactness that we see in all these experiments follows from the threshold choice (see Remark 3). The threshold of Chang et al. [4 ] allows more null statistics to cross in some runs, producing more variable CPDAG collections. Our proposed threshold suppresses these crossings, yielding smaller confidence balls and narrower intervals.
Stable edges from confidence intervals. The lower and upper graphs of the model confidence interval also provide an edge-level summary of structural uncertainty. Any edge that appears in both endpoints is present throughout the interval and is therefore supported across all CPDAGs represented by the interval. Table 2 reports the number of such shared edges across sample sizes. As n n n increases, the number of shared edges grows, reflecting increasing agreement between the lower and upper graphs and greater certainty about the underlying structure.
Table 2. Average number of edges shared by the lower and upper graphs of the model confidence interval across sample sizes. Results are averaged over the 600 instances.
Simulations on computational performance
We explore the extent to which the theoretical results of § 5 improve our computations. We first evaluate the computation of model-oriented distances needed for confidence balls in three regimes: nearly decomposable graphs, graphs close to being polytrees, and graph pairs with many local mismatch configurations. We then evaluate the computation of lower graphs needed for confidence intervals across different graph sizes and densities.
Setup
Given two CPDAGs, we record a timeout if the requested lower graph or model-oriented distance is not certified within 60 seconds. To assess performance under smaller computational budgets, we also consider
b ∈ { 0.001 , 0.003 , 0.01 , 0.03 , 0.1 , 0.3 , 1 , 3 , 10 , 30 , 60 } seconds . b \in\{0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30, 60\}\ \text{seconds}. b ∈ { 0.001 , 0.003 , 0.01 , 0.03 , 0.1 , 0.3 , 1 , 3 , 10 , 30 , 60 } seconds .
A run is counted as a timeout at budget b b b if its completion time exceeds b b b . We use the same graph pairs across all budgets and report one-standard-deviation bands around the timeout proportions.
We compare our methods with those of Taeb et al. [53 ] . For model-oriented distance, their procedure uses exact down-up and up-down paths as upper bounds and the exact forbidden-triple mismatch bound as its lower bound. For lower-graph computation, their method uses the skeleton intersection as its heuristic, completes through the least CPDAG, and has no finite initial upper bound. § 6 describes our corresponding search strategies.
Model-oriented distance computation under structural proximity
Disconnected components
We next study the extent to which Theorem 3 improves computation of model-oriented distance for graphs that are nearly decomposable. We consider
q i n = 0.7 , m ∈ { 0 , 1 , 3 , 7 } , q_{\mathrm{in}} = 0.7,\qquad m \in\{0,1,3,7\}, q in = 0.7 , m ∈ { 0 , 1 , 3 , 7 } ,
with p ∈ { 10 , 15 , 20 , 30 , 100 } p \in\{10, 15, 20, 30, 100\} p ∈ { 10 , 15 , 20 , 30 , 100 } and block sizes three and five. Vertices are partitioned as evenly as possible among the blocks. The start and target graphs share this partition. Conditional on a random topological ordering, within-block edges are included independently with probability q i n q_{\mathrm{in}} q in , and exactly m m m cross-block edges are added uniformly at random and oriented according to the same ordering. Start and target DAGs are generated independently and converted to CPDAGs. For each setting, we generate 100 pairs.
We compute model-oriented distance with the A* procedure of Taeb et al. [53 ] , our search without the disconnected-component upper bound, and the same search with the upper bound enabled. All other search components are held fixed. Figure 13 reports timeout rates across computational budgets. When m = 0 m = 0 m = 0 , the component upper bound is exact, so our procedure returns it immediately.
Figure 13. Timeout rates for model-oriented distance searches between CPDAG pairs in the disconnected-component regime, with q i n = 0.7 q_{\mathrm{in}} = 0.7 q in = 0.7 and m ∈ { 0 , 1 , 3 , 7 } m \in\{0,1,3,7\} m ∈ { 0 , 1 , 3 , 7 } . Columns correspond to p = 10 , 15 , 20 , 30 , p = 10, 15, 20, 30, p = 10 , 15 , 20 , 30 , and 100 100 100 ; rows correspond to m m m . Solid and dashed curves use block sizes three and five, respectively. Each point is the proportion of the 100 pairs not solved within the indicated time budget; shaded regions show one standard deviation around that proportion. The curves compare the model-oriented-distance A∗ ^{*} ∗ procedure of Taeb et al. [53 ] with our procedure without the disconnected-component upper bound and with our procedure using the disconnected-component upper bound.
The search using the disconnected-component upper bound has the lowest timeout rate in nearly every setting. For m = 0 m = 0 m = 0 , the exact bound makes its timeout rate fall to zero almost immediately at every graph size. The advantage of the bound remains pronounced for m > 0 m > 0 m > 0 , particularly at p = 30 p = 30 p = 30 and p = 100 p = 100 p = 100 : with block size three, it solves nearly all pairs within the budget grid even as m m m increases, while the procedures without the bound retain substantial timeout rates. For block size five, its timeout rate rises with m m m , reflecting the weaker decomposition, but it remains below the competing procedures. The procedure of Taeb et al. [53 ] times out on most pairs at the larger graph sizes. We include timeout rates for q i n = 0.5 q_{\mathrm{in}} = 0.5 q in = 0.5 in Appendix E.§ 2 .
Polytrees
We next study the extent to which Theorem 4 improves computation of the model-oriented distance for graphs near the polytree class. We use
p ∈ { 10 , 15 , 20 , 30 , 100 } , q t r e e = 0.8 , c ∈ { 0 , 1 , 3 , 7 } . p \in\{10, 15, 20, 30, 100\}, \qquad q_{\mathrm{tree}} = 0.8, \qquad c \in\{0,1,3,7\}. p ∈ { 10 , 15 , 20 , 30 , 100 } , q tree = 0.8 , c ∈ { 0 , 1 , 3 , 7 } .
For each graph, we sample a uniformly random labeled tree using Wilson [58 ] , and retain each edge independently with probability q t r e e q_{\mathrm{tree}} q tree . This produces a forest. We orient the retained edges according to a random topological ordering and then add c c c edges between previously non-adjacent vertices in the same connected component, orienting them according to the ordering. Thus, c c c controls the departure from polytree structure. Start and target graphs are generated independently and converted to CPDAGs. For each setting, we generate 100 unique pairs.
We compute model-oriented distance with the A∗ ^{*} ∗ procedure of Taeb et al. [53 ] , our search without the polytree upper bound, and the same search with the upper bound enabled. All other search components are held fixed. Figure 14 reports timeout rates across computational budgets. When c = 0 c = 0 c = 0 , the polytree upper bound is exact, so our procedure returns it immediately.
Figure 14. Timeout rates for model-oriented distance searches between CPDAG pairs near the polytree class, with q t r e e = 0.8 q_{\mathrm{tree}} = 0.8 q tree = 0.8 and c ∈ { 0 , 1 , 3 , 7 } c \in\{0, 1, 3, 7\} c ∈ { 0 , 1 , 3 , 7 } . Columns correspond to p = 10 , 15 , 20 , 30 , p = 10, 15, 20, 30, p = 10 , 15 , 20 , 30 , and 100 100 100 ; rows correspond to c c c . Each point is the proportion of the 100 pairs not solved within the indicated time budget; shaded regions show one standard deviation around that proportion. The curves compare the model-oriented-distance A* procedure of Taeb et al. [53 ] with our procedure without the polytree upper bound and with our procedure using the polytree upper bound.
The search using the polytree upper bound has the lowest timeout rate in nearly every setting. For c = 0 c = 0 c = 0 , the exact bound makes its timeout rate fall to zero almost immediately at every graph size. For c > 0 c > 0 c > 0 , its advantage over the search without the bound grows with p p p : at p = 30 p = 30 p = 30 and p = 100 p = 100 p = 100 , it substantially reduces timeouts at moderate and large budgets, while the search without the bound remains well above zero. The procedure of Taeb et al. [53 ] times out on most pairs at the larger graph sizes, including at the largest budget. We include timeout rates for q t r e e = 0.5 q_{\mathrm{tree}} = 0.5 q tree = 0.5 and q t r e e = 1 q_{\mathrm{tree}} = 1 q tree = 1 in Appendix E.§ 2 .
Lower bounds from mismatch structure
We next study the utility of the mismatch lower bound of Theorem 5 and its independent-set approximation from Corollary 2 for computing the model-oriented distance. We construct connected chains of overlapping four-node mismatch configurations with p ∈ { 7 , 10 , 22 , 28 } p \in\{7, 10, 22, 28\} p ∈ { 7 , 10 , 22 , 28 } , p = 3 K + 1 p = 3K + 1 p = 3 K + 1 .
Here, K K K represents the number of four-node blocks. Successive blocks share one vertex. We construct a start and a target DAG from overlapping four-node configurations. For each block, we independently sample one of the four mismatch types in Figure 7 (b) and Figure 8 (a)–(Figure 8 c), and place the corresponding paired configurations in the start and target DAGs, respectively. We convert both DAGs to CPDAGs. For each setting, we generate 100 unique pairs of CPDAGs.
We compare the model-oriented-distance A* procedure of Taeb et al. [53 ] with four variants of our procedure: exact and independent-set computations of the lower bound using only forbidden triples, illustrated in Figure 7 (a), and using all five mismatch types (dubbed “all-mismatch”). All other search components are held fixed. Figure 15 reports timeout rates across computational budgets.
Figure 15. Timeout rates for model-oriented distance searches between CPDAG pairs constructed from connected chains of overlapping four-node mismatch blocks. The panels correspond to p = 7 p = 7 p = 7 , 10 10 10 , 22 22 22 , and 28 28 28 . Each point is the proportion of the 100 pairs not solved within the indicated time budget, with shaded regions showing one standard deviation. The curves compare the A* procedure of Taeb et al. [53 ] with four variants of our procedure: exact and independent-set lower-bound computations using forbidden triples alone or all five mismatch types.
The search using the exact all-mismatch bound has the lowest timeout rate at each graph size. For p = 7 p = 7 p = 7 and p = 10 p = 10 p = 10 , the timeout rate reaches zero at small budgets. The search using the forbidden-triple bounds requires more time, while the procedure of Taeb et al. [53 ] remains substantially slower. The differences become more pronounced for p = 22 p = 22 p = 22 and p = 28 p = 28 p = 28 . At these large graph sizes, the search using the exact all-mismatch bound improves substantially with additional time. In contrast, the search using the all-mismatch independent-set bound plateaus near 80% and 95%, respectively. The searches using the forbidden-triple bounds and the procedure of Taeb et al. [53 ] remain at or near 100% timeouts.
Common lower graphs
Finally, we ask whether the construction of Proposition 2 improves lower-graph computation relative to the procedure of Taeb et al. [53 ] .
We generate random CPDAGs by first sampling a uniformly random ordering of p p p labeled vertices. For each pair of vertices, we then include an edge independently with probability q q q and orient it from the earlier to the later vertex in the sampled ordering. We convert the resulting DAG to its CPDAG. We consider
p ∈ { 10 , 12 , 15 , 20 } , q ∈ { 0.2 , 0.5 } . p \in\{10, 12, 15, 20\}, \qquad q \in\{0.2, 0.5\}. p ∈ { 10 , 12 , 15 , 20 } , q ∈ { 0.2 , 0.5 } .
For each ( p , q ) (p, q) ( p , q ) , we generate 100 independent CPDAG pairs, resampling when the two graphs are identical. We then compute common lower graphs using the procedure of Taeb et al. [53 ] and our procedure. Figure 16 reports timeout rates over the full budget grid.
Figure 16. Timeout rates for computation of common lower graphs. Panels correspond to p = 10 p = 10 p = 10 , 12 12 12 , 15 15 15 , and 20 20 20 . Solid and dotted curves correspond to q = 0.2 q = 0.2 q = 0.2 and q = 0.5 q = 0.5 q = 0.5 , respectively. Each point is the proportion of the 100 pairs not solved within the indicated time budget; shaded regions show one standard deviation. The curves compare the procedure of Taeb et al. [53 ] with our procedure.
Our procedure has lower timeout rates in nearly every setting. The improvement is most pronounced for the sparse graphs at p = 15 p = 15 p = 15 and p = 20 p = 20 p = 20 , where our timeout rate approaches zero while that of Taeb et al. [53 ] remains substantially higher. The dense instances are more difficult for both procedures, although our procedure continues to improve with additional time at p = 10 p = 10 p = 10 and p = 12 p = 12 p = 12 .
Discussion
We first analyzed the perturbed PC algorithm and proposed a threshold that tightened the collection of plausible CPDAGs while preserving asymptotic coverage. The threshold filtered out most null statistics across runs while allowing weak signals to survive in at least one run, without requiring strong faithfulness. We then used the CPDAG poset under model inclusion to summarize this collection through confidence balls and model confidence intervals. The confidence ball measured structural uncertainty through a shortest path distance from the PC estimate, while the confidence interval bracketed the true CPDAG between common lower and upper graphs. Finally, we developed new computational theory for constructing both regions. Sharper distance bounds, exact decomposition across disconnected components, exact characterization for polytrees, and new bounds for common lower and upper graphs substantially reduced the search space. Simulations showed that the resulting regions attained good coverage while being substantially smaller than regions constructed from the original perturbed PC collections.
Our work opens several directions for future research. First, our guarantees treat the number of variables p p p as fixed. Extending them to p → ∞ p \to\infty p → ∞ would require uniform control of sample partial correlations and of the growing number of conditional independence tests. Second, kernel conditional independence tests could relax the linear Gaussian assumptions. Their null distributions depend on unknown features of the joint distribution, which complicates calibration of the perturbations. Third, our model confidence intervals construct the lower and upper models sequentially. This procedure guarantees a valid interval containing the perturbed PC collection, but it need not produce the smallest possible interval. A natural extension is to optimize the two endpoints jointly to obtain a minimum width valid interval. Finally, exact computation remains costly for dense graphs that do not decompose into simpler structures. Approximate computations can still yield valid regions because upper bounds on the radius and feasible interval endpoints only enlarge the regions. A natural direction is therefore to relate computational suboptimality to statistical conservativeness, for example by bounding how much an early-stopped search can inflate the ball radius or interval width.
Acknowledgments
We gratefully acknowledge the Washington Experimental Mathematics Lab at the University of Washington for bringing undergraduates Jian Kang and Arnav Mazumder together with Armeen Taeb through this project. Simulations for this work were completed on Hyak, the University of Washington’s high performance computing cluster. This resource was funded by the UW student technology fee.
The PC and Tiered PC algorithms
The standard PC algorithm
We use the PC algorithm of Spirtes et al. [48 ] with the statistic T ^ i j ∣ S \widehat{T}_{ij\mid S} T ij ∣ S of § 4.1 . A test rejects conditional independence when T ^ i j ∣ S > t \widehat{T}_{ij\mid S}>t T ij ∣ S > t . Otherwise, PC deletes the edge i − j i-j i − j and records sepset ( i , j ) = sepset ( j , i ) = S \operatorname{sepset}(i,j)=\operatorname{sepset}(j,i)=S sepset ( i , j ) = sepset ( j , i ) = S . The algorithm has three stages. The skeleton stage starts from the complete graph. For ℓ = 0 , 1 , … \ell=0,1,\ldots ℓ = 0 , 1 , … , it tests each remaining adjacent pair ( i , j ) (i,j) ( i , j ) given the subsets S S S of size ℓ \ell ℓ of the current neighbors of i i i , examining pairs and subsets in a fixed order. The v-structure stage orients each unshielded triple i − k − j i-k-j i − k − j as i → k ← j i\to k\leftarrow j i → k ← j if and only if k ∉ sepset ( i , j ) k\notin\operatorname{sepset}(i,j) k ∈ / sepset ( i , j ) . The propagation stage applies the rules R 1 R_1 R 1 –R 4 R_4 R 4 of Meek [32 ] until no further edge can be oriented. In run m m m of Algorithm 1, T ^ i j ∣ S \widehat{T}_{ij\mid S} T ij ∣ S is replaced by T ^ i j ∣ S [ m ] \widehat{T}_{ij\mid S}^{[m]} T ij ∣ S [ m ] , and all graphical steps are unchanged.
A run is invalid if two v-structures require opposite orientations of an edge, if propagation produces a conflict, or if the output is not a CPDAG. Finite-sample errors can produce each of these outcomes, and an acyclic output need not be a CPDAG. Algorithm 1 discards invalid runs.
When every test decision is correct, PC returns G ∗ G^* G ∗ under Assumption 1 (Kalisch and Bühlmann, [24 ] ; Spirtes et al. [48 ] ). § 4.2 uses only this property, so the analysis applies to both the order-dependent version of PC and PC-stable (Colombo and Maathuis, [9 ] ).
The tiered PC algorithm
A tier assignment O : V → { 1 , … , K } O:V\to\{1,\ldots,K\} O : V → { 1 , … , K } , written as O ( V ) = ( O ( 1 ) , … , O ( p ) ) O(V)=(O(1),\ldots,O(p)) O ( V ) = ( O ( 1 ) , … , O ( p )) , places the variables in ordered temporal tiers. If O ( i ) < O ( j ) O(i)<O(j) O ( i ) < O ( j ) , then X i X_i X i precedes X j X_j X j , so j → i j\to i j → i is forbidden. No ordering is imposed within a tier. We assume that the true underlying DAG respects the tier assignment.
Following Chang et al. [4 ] , we use the PC-stable search of Colombo and Maathuis [9 ] and incorporate the tiers into both skeleton estimation and edge orientation. The test statistics T ^ i j ∣ S \widehat{T}_{ij\mid S} T ij ∣ S and threshold t > 0 t>0 t > 0 are unchanged.
Algorithm 4: Tiered PC algorithm with CPDAG output
Input: Data D \mathcal{D} D , threshold t > 0 t > 0 t > 0 , and tier assignment O ( V ) O(V) O ( V ) .
Output: A CPDAG estimate G ^ n ∈ G \widehat{G}_n \in\mathcal{G} G n ∈ G , or INVALID.
Initialize G ← G f u l l \mathcal{G} \leftarrow\mathcal{G}_{\mathrm{full}} G ← G full and all separating sets as undefined;
for ℓ = 0 , … , p − 2 \ell= 0, \ldots, p - 2 ℓ = 0 , … , p − 2 do
Store adj ~ ℓ ( i ) ← adj ( G , i ) \widetilde{\operatorname{adj}}_{\ell}(i) \leftarrow\operatorname{adj}(\mathcal{G}, i) adj ℓ ( i ) ← adj ( G , i ) for all i ∈ V i \in V i ∈ V ;
Form A ℓ , i j A_{\ell,ij} A ℓ , ij as in (8) ;
if ∣ A ℓ , i j ∣ < ℓ |A_{\ell,ij}| < \ell ∣ A ℓ , ij ∣ < ℓ for every ordered adjacent pair ( i , j ) (i,j) ( i , j ) then
break;
foreach ordered adjacent pair ( i , j ) (i,j) ( i , j ) with ∣ A ℓ , i j ∣ ≥ ℓ |A_{\ell,ij}| \ge\ell ∣ A ℓ , ij ∣ ≥ ℓ do
Test sets S ⊆ A ℓ , i j S \subseteq A_{\ell,ij} S ⊆ A ℓ , ij of size ℓ \ell ℓ in a fixed order, stopping at the first with T ^ i j ∣ S ≤ t \widehat{T}_{ij\mid S} \le t T ij ∣ S ≤ t ;
if such a set S S S is found then
Delete i − j i-j i − j from G \mathcal{G} G ;
sepset ( i , j ) = sepset ( j , i ) ← S \operatorname{sepset}(i,j) = \operatorname{sepset}(j,i) \leftarrow S sepset ( i , j ) = sepset ( j , i ) ← S ;
Orient cross-tier edges and identify v-structures, respecting O ( V ) O(V) O ( V ) ;
Apply R 1 R_1 R 1 –R 4 R_4 R 4 until no further edge can be oriented;
if the orientation requirements conflict or no consistent DAG extension exists then
return INVALID;
Convert G \mathcal{G} G to its observational CPDAG G ^ n \widehat{G}_n G n ;
return G ^ n \widehat{G}_n G n ;
Skeleton estimation. Start from G f u l l \mathcal{G}_{\mathrm{full}} G full . At each conditioning-set size ℓ \ell ℓ , store the current adjacency sets adj ℓ ( i ) : = adj ( G , i ) \operatorname{adj}_{\ell}(i) := \operatorname{adj}(\mathcal{G},i) adj ℓ ( i ) := adj ( G , i ) and define
A ℓ , i j : = { k ∈ adj ~ ℓ ( i ) ∖ { j } : O ( k ) ≤ max { O ( i ) , O ( j ) } } . (8) A_{\ell,ij} := \{k \in\widetilde{\operatorname{adj}}_{\ell}(i) \setminus\{j\} : O(k) \le\max\{O(i),O(j)\}\}. \tag*{(8)} A ℓ , ij := { k ∈ adj ℓ ( i ) ∖ { j } : O ( k ) ≤ max { O ( i ) , O ( j )}} . (8)
Thus, conditioning variables cannot lie in a tier later than both endpoints. For each ordered adjacent pair ( i , j ) (i,j) ( i , j ) , test subsets S ⊆ A ℓ , i j S \subseteq A_{\ell,ij} S ⊆ A ℓ , ij of size ℓ \ell ℓ . At the first set satisfying T ^ i j ∣ S ≤ t \widehat{T}_{ij\mid S} \le t T ij ∣ S ≤ t , delete i − j i-j i − j and record sepset ( i , j ) = sepset ( j , i ) ← S \operatorname{sepset}(i,j) = \operatorname{sepset}(j,i) \leftarrow S sepset ( i , j ) = sepset ( j , i ) ← S . Pairs and conditioning sets are examined in a fixed order. Deletions take effect immediately, but the stored adjacency sets remain fixed throughout level ℓ \ell ℓ . Stop when ∣ A ℓ , i j ∣ < ℓ |A_{\ell,ij}| < \ell ∣ A ℓ , ij ∣ < ℓ for every remaining ordered adjacent pair. When O ( i ) ≡ 1 O(i) \equiv1 O ( i ) ≡ 1 , this reduces to the unrestricted PC-stable search.
Edge orientation. Orient each edge between distinct tiers from the earlier to the later tier. For each unshielded triple ( i , k , j ) (i,k,j) ( i , k , j ) in the estimated skeleton, impose i → k ← j i \to k \leftarrow j i → k ← j if and only if k ∉ sepset ( i , j ) k \notin\operatorname{sepset}(i,j) k ∈ / sepset ( i , j ) . Then apply Meek’s rules R 1 R_1 R 1 –R 4 R_4 R 4 (Meek, [32 ] ) until no further edge can be oriented. All orientations must be compatible with the tier assignment and the recorded separating sets.
CPDAG output. With tier restrictions, a valid output is generally a maximally oriented partially directed acyclic graph (MPDAG) (Bang and Didelez, [2 ] ). We convert this graph to its observational CPDAG so that our confidence regions remain subsets of G \mathcal{G} G . Specifically, choose a consistent DAG extension: a DAG with the same skeleton that preserves all directed edges and introduces no new v-structures. Return the CPDAG of its Markov equivalence class. All consistent extensions have the same skeleton and v-structures, so the choice of extension does not affect the returned CPDAG. If the orientation requirements conflict or no consistent DAG extension exists, the run is invalid.
Algorithm 4 summarizes the procedure. For run m m m of perturbed PC, replace T ^ i j ∣ S \widehat{T}_{ij\mid S} T ij ∣ S by T ^ i j ∣ S [ m ] \widehat{T}_{ij\mid S}^{[m]} T ij ∣ S [ m ] ; all graphical steps remain unchanged.
Proofs for Section 4.2
Throughout, write Φ ˉ : = 1 − Φ \bar{\Phi}:=1-\Phi Φ ˉ := 1 − Φ . Given the data D \mathcal{D} D , the U ^ l [ m ] \widehat{U}^{[m]}_l U l [ m ] are independent N ( 0 , η n 2 ) \mathcal{N}(0,\eta_n^2) N ( 0 , η n 2 ) over l ∈ T l\in\mathcal{T} l ∈ T and m ≤ M n m\le M_n m ≤ M n . Run m m m decides a test in T n u l l \mathcal{T}_{\mathrm{null}} T null correctly if T ^ l [ m ] ≤ t n \widehat{T}^{[m]}_l\le t_n T l [ m ] ≤ t n , and a test in T ∖ T n u l l \mathcal{T}\setminus\mathcal{T}_{\mathrm{null}} T ∖ T null correctly if T ^ l [ m ] > t n \widehat{T}^{[m]}_l>t_n T l [ m ] > t n . We interpret empty products as one.
Proof of Lemma 1. Fix the data and suppose that E n E_n E n holds. Fix l ∈ T n u l l l\in\mathcal{T}_{\mathrm{null}} l ∈ T null . Then ψ l = 0 \psi_l=0 ψ l = 0 , so T ^ l [ m ] = ∣ U ^ l + U ^ l [ m ] ∣ \widehat{T}^{[m]}_l=\lvert\widehat{U}_l+\widehat{U}^{[m]}_l\rvert T l [ m ] = ∣ U l + U l [ m ] ∣ . Conditional on the observed data:
P ( T ^ l [ m ] ≤ t ∣ D ) = P ( − t ≤ U ^ l + U ^ l [ m ] ≤ t ∣ D ) . \mathbb{P}(\widehat{T}^{[m]}_l\le t\mid\mathcal{D})=\mathbb{P}(-t\le\widehat{U}_l+\widehat{U}^{[m]}_l\le t\mid\mathcal{D}). P ( T l [ m ] ≤ t ∣ D ) = P ( − t ≤ U l + U l [ m ] ≤ t ∣ D ) .
Because U ^ l \widehat{U}_l U l is fixed given the data, this equals:
P ( − t − U ^ l ≤ U ^ l [ m ] ≤ t − U ^ l ∣ D ) = Φ ( t − U ^ l η ) − Φ ( − t − U ^ l η ) . \mathbb{P}(-t-\widehat{U}_l\le\widehat{U}^{[m]}_l\le t-\widehat{U}_l\mid\mathcal{D})=\Phi\left(\frac{t-\widehat{U}_l}{\eta}\right)-\Phi\left(\frac{-t-\widehat{U}_l}{\eta}\right). P ( − t − U l ≤ U l [ m ] ≤ t − U l ∣ D ) = Φ ( η t − U l ) − Φ ( η − t − U l ) .
Note that the function g ( u ) = Φ ( ( t − u ) / η ) − Φ ( ( − t − u ) / η ) g(u)=\Phi((t-u)/\eta)-\Phi((-t-u)/\eta) g ( u ) = Φ (( t − u ) / η ) − Φ (( − t − u ) / η ) is even and is nonincreasing as ∣ u ∣ \lvert u\rvert ∣ u ∣ increases. Since ∣ U ^ l ∣ ≤ z \lvert\widehat{U}_l\rvert\le z ∣ U l ∣ ≤ z on E n E_n E n , we have that:
P ( T ^ l [ m ] ≤ t ∣ D ) ≥ Φ ( t − z η ) − Φ ( − t − z η ) . \mathbb{P}(\widehat{T}^{[m]}_l\le t\mid\mathcal{D})\ge\Phi\left(\frac{t-z}{\eta}\right)-\Phi\left(\frac{-t-z}{\eta}\right). P ( T l [ m ] ≤ t ∣ D ) ≥ Φ ( η t − z ) − Φ ( η − t − z ) .
For l ∈ T ∖ T n u l l l\in\mathcal{T}\setminus\mathcal{T}_{\mathrm{null}} l ∈ T ∖ T null , let h l = sign ( ψ l ) h_l=\operatorname{sign}(\psi_l) h l = sign ( ψ l ) . Note that:
T ^ l [ m ] = ∣ h l ( ψ l σ l + U ^ l + U ^ l [ m ] ) ∣ = ∣ κ l + h l U ^ l + h l U ^ l [ m ] ∣ . \widehat{T}^{[m]}_l=\left\lvert h_l\left(\frac{\psi_l}{\sigma_l}+\widehat{U}_l+\widehat{U}^{[m]}_l\right)\right\rvert=\left\lvert\kappa_l+h_l\widehat{U}_l+h_l\widehat{U}^{[m]}_l\right\rvert. T l [ m ] = h l ( σ l ψ l + U l + U l [ m ] ) = κ l + h l U l + h l U l [ m ] .
Therefore, we have:
P ( T ^ l [ m ] > t ∣ D ) ≥ P ( κ l + h l U ^ l + h l U ^ l [ m ] > t ∣ D ) = Φ ( κ l + h l U ^ l − t η ) ≥ Φ ( κ l − z − t η ) . \begin{aligned}
\mathbb{P}(\widehat{T}^{[m]}_l>t\mid\mathcal{D})
&\ge\mathbb{P}(\kappa_l+h_l\widehat{U}_l+h_l\widehat{U}^{[m]}_l>t\mid\mathcal{D})\\
&=\Phi\left(\frac{\kappa_l+h_l\widehat{U}_l-t}{\eta}\right)\\
&\ge\Phi\left(\frac{\kappa_l-z-t}{\eta}\right).
\end{aligned} P ( T l [ m ] > t ∣ D ) ≥ P ( κ l + h l U l + h l U l [ m ] > t ∣ D ) = Φ ( η κ l + h l U l − t ) ≥ Φ ( η κ l − z − t ) .
The last inequality uses h l U ^ l ≥ − z h_l\widehat{U}_l\ge-z h l U l ≥ − z on E n E_n E n . The perturbations are independent across tests, so the event that all tests in T \mathcal{T} T are decided correctly has conditional probability at least π \pi π . The event is sufficient for the run to be correct. The perturbations are also independent across runs, so some run is correct with conditional probability at least 1 − ( 1 − π ) M 1-(1-\pi)^M 1 − ( 1 − π ) M , and every run is correct with conditional probability at least π M \pi^M π M . Taking expectations over E n E_n E n gives both bounds. □ \square □
Proof of Theorem 2. By Lemma 1 and 1 − x ≤ e − x 1-x\le e^{-x} 1 − x ≤ e − x ,
P ( G ⋆ ∈ G ^ n ) ≥ ( 1 − e − M n π n ) P ( E n ) , (9) \mathbb{P}\left(\mathcal{G}^{\star}\in\widehat{\mathcal{G}}_n\right)\ge\left(1-e^{-M_n\pi_n}\right)\mathbb{P}(E_n), \tag*{(9)} P ( G ⋆ ∈ G n ) ≥ ( 1 − e − M n π n ) P ( E n ) , (9)
and lim inf n P ( E n ) ≥ 1 − ν \liminf_n\mathbb{P}(E_n)\ge1-\nu lim inf n P ( E n ) ≥ 1 − ν . Recall that:
π n : = { Φ ( t n − z η n ) − Φ ( − t n − z η n ) } L 0 ∏ l ∈ T n o n − n u l l Φ ( κ l − z − t n η n ) . \pi_n:=\left\{\Phi\left(\frac{t_n-z}{\eta_n}\right)-\Phi\left(\frac{-t_n-z}{\eta_n}\right)\right\}^{L_0}\prod_{l\in\mathcal{T}_{\mathrm{non-null}}}\Phi\left(\frac{\kappa_l-z-t_n}{\eta_n}\right). π n := { Φ ( η n t n − z ) − Φ ( η n − t n − z ) } L 0 l ∈ T non − null ∏ Φ ( η n κ l − z − t n ) .
(a)(i). Since t n t_n t n is bounded, let t n ≤ t ˉ t_n\le\bar{t} t n ≤ t ˉ . Recall, η ≤ η n ≤ η ˉ \eta\le\eta_n\le\bar{\eta} η ≤ η n ≤ η ˉ , with η > 0 \eta>0 η > 0 . For each null test, the corresponding factor of π n \pi_n π n is
Φ ( t n − z η n ) − Φ ( − t n − z η n ) . \Phi\left(\frac{t_n-z}{\eta_n}\right)-\Phi\left(\frac{-t_n-z}{\eta_n}\right). Φ ( η n t n − z ) − Φ ( η n − t n − z ) .
This is the probability that a standard normal random variable lies in the interval [ ( − t n − z ) / η n , ( t n − z ) / η n ] [(-t_n-z)/\eta_n,(t_n-z)/\eta_n] [( − t n − z ) / η n , ( t n − z ) / η n ] . The interval has length 2 t n / η n ≥ 2 t n / η ˉ 2t_n/\eta_n\ge2t_n/\bar{\eta} 2 t n / η n ≥ 2 t n / η ˉ and is contained in
[ − t ˉ + z η , t ˉ + z η ] . \left[-\frac{\bar{t}+z}{\eta},\frac{\bar{t}+z}{\eta}\right]. [ − η t ˉ + z , η t ˉ + z ] .
The probability that a standard normal lies in this interval is bounded below by
2 t ˉ η Φ ( t ˉ + z η ) . \frac{2\bar{t}}{\eta} \Phi\left(\frac{\bar{t}+z}{\eta}\right). η 2 t ˉ Φ ( η t ˉ + z ) .
For each non-null test, the corresponding factor in π n \pi_n π n is bounded below by the positive constant Φ ( − ( t ˉ + z ) / η ) \Phi\left(-(\bar{t}+z)/\eta\right) Φ ( − ( t ˉ + z ) / η ) . Hence, for some constant C > 0 C>0 C > 0 , π n ≥ C t n L 0 \pi_n \ge Ct_n^{L_0} π n ≥ C t n L 0 . Since M n t n L 0 → ∞ M_n t_n^{L_0} \to\infty M n t n L 0 → ∞ , we obtain M n π n → ∞ M_n\pi_n \to\infty M n π n → ∞ . Plugging this into (9) gives the desired result.
(a)(ii). For a null test, the corresponding factor of π n \pi_n π n is
Φ ( t n − z η n ) − Φ ( − t n − z η n ) . \Phi\left(\frac{t_n-z}{\eta_n}\right)-\Phi\left(\frac{-t_n-z}{\eta_n}\right). Φ ( η n t n − z ) − Φ ( η n − t n − z ) .
Since z z z is a constant and η n \eta_n η n is bounded above by a constant η ˉ \bar{\eta} η ˉ , and t n → ∞ t_n \to\infty t n → ∞ , we have t n − z > 0 t_n-z>0 t n − z > 0 for all large n n n . For such n n n :
t n − z η n ≥ t n − z η ˉ → ∞ , \frac{t_n-z}{\eta_n} \ge\frac{t_n-z}{\bar{\eta}} \to\infty, η n t n − z ≥ η ˉ t n − z → ∞ ,
− t n − z η n ≤ − t n − z η ˉ → − ∞ . \frac{-t_n-z}{\eta_n} \le\frac{-t_n-z}{\bar{\eta}} \to-\infty. η n − t n − z ≤ η ˉ − t n − z → − ∞.
Hence, every null factor tends to one. Now split the nonnull tests into strong and weak tests. Let:
T s t r o n g = { l ∈ T n o n − n u l l , κ l − t n → ∞ } , \mathcal{T}_{\mathrm{strong}}=\{l\in\mathcal{T}_{\mathrm{non-null}},\ \kappa_l-t_n\to\infty\}, T strong = { l ∈ T non − null , κ l − t n → ∞ } ,
and let W W W denote the set of weak nonnull tests. For each strong nonnull test l l l , we have κ l − t n − z > 0 \kappa_l-t_n-z>0 κ l − t n − z > 0 for all large n n n . For such n n n :
κ l − t n − z η n ≥ κ l − t n − z η ˉ → ∞ , \frac{\kappa_l-t_n-z}{\eta_n}\ge\frac{\kappa_l-t_n-z}{\bar{\eta}}\to\infty, η n κ l − t n − z ≥ η ˉ κ l − t n − z → ∞ ,
so its factor
Φ ( κ l − z − t n η n ) → 1. \Phi\left(\frac{\kappa_l-z-t_n}{\eta_n}\right)\to1. Φ ( η n κ l − z − t n ) → 1.
Define:
μ n : = ( Φ ( t n − z η n ) − Φ ( − t n − z η n ) ) L 0 ∏ l ∈ T s t r o n g Φ ( κ l − z − t n η n ) . \mu_n:=\left(\Phi\left(\frac{t_n-z}{\eta_n}\right)-\Phi\left(\frac{-t_n-z}{\eta_n}\right)\right)^{L_0}\prod_{l\in\mathcal{T}_{\mathrm{strong}}}\Phi\left(\frac{\kappa_l-z-t_n}{\eta_n}\right). μ n := ( Φ ( η n t n − z ) − Φ ( η n − t n − z ) ) L 0 l ∈ T strong ∏ Φ ( η n κ l − z − t n ) .
Then, μ n → 1 \mu_n\to1 μ n → 1 . Fix a realization D ∈ E n \mathcal{D}\in E_n D ∈ E n . By the same bounds used to construct π n \pi_n π n ,
P ( all null tests and strong nonnull tests are correct in run m ∣ D ) ≥ μ n . \mathbb{P}(\text{all null tests and strong nonnull tests are correct in run }m\mid\mathcal{D})\ge\mu_n. P ( all null tests and strong nonnull tests are correct in run m ∣ D ) ≥ μ n .
If W = ∅ W=\varnothing W = ∅ , then all tests are either null or strong nonnull, so π n = μ n → 1 \pi_n=\mu_n\to1 π n = μ n → 1 . On E n E_n E n , the first run is correct with conditional probability tending to one, and Lemma 1 gives coverage.
Now suppose W ≠ ∅ W\ne\varnothing W = ∅ . For each run m ≤ M n m\le M_n m ≤ M n , define:
A m : = { U ~ l [ m ] ≥ r n ( L w e a k ) for all l ∈ W } , A_m:=\left\{\widetilde{U}_l^{[m]}\ge r_n(L_{\mathrm{weak}})\text{ for all }l\in W\right\}, A m := { U l [ m ] ≥ r n ( L weak ) for all l ∈ W } ,
where U ~ l [ m ] = sign ( ψ l ) U ^ l [ m ] \widetilde{U}_l^{[m]}=\operatorname{sign}(\psi_l)\widehat{U}_l^{[m]} U l [ m ] = sign ( ψ l ) U l [ m ] . By definition of r n ( L w e a k ) r_n(L_{\mathrm{weak}}) r n ( L weak ) ,
P ( ⋃ m ≤ M n A m ∣ D ) = 1 − δ n → 1. \mathbb{P}\left(\left.\bigcup_{m\le M_n}A_m\right|\mathcal{D}\right)=1-\delta_n\to1. P ( m ≤ M n ⋃ A m D ) = 1 − δ n → 1.
On the event ⋃ m ≤ M n A m \bigcup_{m\le M_n}A_m ⋃ m ≤ M n A m , let m ⋆ m^\star m ⋆ be the first run for which A m A_m A m occurs. Notice that:
P ( m ⋆ exists ∣ D ) = 1 − δ n → 1. \mathbb{P}(m^\star\text{ exists}\mid\mathcal{D})=1-\delta_n\to1. P ( m ⋆ exists ∣ D ) = 1 − δ n → 1.
Now fix m m m and condition on m ⋆ = m m^\star=m m ⋆ = m . Since m ⋆ = m m^\star=m m ⋆ = m implies A m A_m A m , for every l ∈ W l\in W l ∈ W ,
T ^ l [ m ⋆ ] ≥ κ l − z + r n ( L w e a k ) . \widehat{T}_l^{[m^\star]}\ge\kappa_l-z+r_n(L_{\mathrm{weak}}). T l [ m ⋆ ] ≥ κ l − z + r n ( L weak ) .
Because
κ l − t n + r n ( L w e a k ) → ∞ , \kappa_l-t_n+r_n(L_{\mathrm{weak}})\to\infty, κ l − t n + r n ( L weak ) → ∞ ,
we have, for sufficiently large n n n ,
T ^ l [ m ⋆ ] > t n . \widehat{T}_l^{[m^\star]}>t_n. T l [ m ⋆ ] > t n .
Thus, on E n ∩ { m ⋆ = m } E_n\cap\{m^\star=m\} E n ∩ { m ⋆ = m } , all weak tests are decided correctly for all sufficiently large n n n .
P ( all tests correct in run m ∣ D , m ⋆ = m ) , = P ( all null tests and strong nonnull tests are correct in run m ∣ D , m ⋆ = m ) , = P ( all null tests and strong nonnull tests are correct in run m ∣ D ) , ≥ μ n , \begin{aligned}
\mathbb{P}(\text{all tests correct in run }m\mid\mathcal{D},m^\star=m),\\
=\mathbb{P}(\text{all null tests and strong nonnull tests are correct in run }m\mid\mathcal{D},m^\star=m),\\
=\mathbb{P}(\text{all null tests and strong nonnull tests are correct in run }m\mid\mathcal{D}),\\
\ge\mu_n,
\end{aligned} P ( all tests correct in run m ∣ D , m ⋆ = m ) , = P ( all null tests and strong nonnull tests are correct in run m ∣ D , m ⋆ = m ) , = P ( all null tests and strong nonnull tests are correct in run m ∣ D ) , ≥ μ n ,
for all sufficiently large n n n . Here, the second equality follows from the fact that, conditional on D \mathcal{D} D , the event { m ⋆ = m } \{m^\star=m\} { m ⋆ = m } depends only on the perturbations of the weak tests, which are independent of the perturbations of the null and strong nonnull tests.
Let C m : = { all tests are correct in run m } C_m := \{\text{all tests are correct in run }m\} C m := { all tests are correct in run m } . We then have for every D ∈ E n \mathcal{D} \in E_n D ∈ E n and n n n sufficiently large:
P ( there exists a run in which all tests are correct ∣ D ) , ≥ ∑ m = 1 M n P ( C m , m ⋆ = m ∣ D ) , = ∑ m = 1 M n P ( m ⋆ = m ∣ D ) P ( C m ∣ D , m ⋆ = m ) , ≥ μ n ( 1 − δ n ) → 1. \begin{aligned}
\mathbb{P}(\text{there exists a run in which all tests are correct}\mid\mathcal{D}),\\
\ge\sum_{m=1}^{M_n}\mathbb{P}(C_m,m^\star=m\mid\mathcal{D}),\\
= \sum_{m=1}^{M_n}\mathbb{P}(m^\star=m\mid\mathcal{D})\mathbb{P}(C_m\mid\mathcal{D},m^\star=m),\\
\ge\mu_n(1-\delta_n)\to1.
\end{aligned} P ( there exists a run in which all tests are correct ∣ D ) , ≥ m = 1 ∑ M n P ( C m , m ⋆ = m ∣ D ) , = m = 1 ∑ M n P ( m ⋆ = m ∣ D ) P ( C m ∣ D , m ⋆ = m ) , ≥ μ n ( 1 − δ n ) → 1.
The first inequality follows because
⋃ m = 1 M n { C m , m ⋆ = m } ⊆ { there exists a run in which all tests are correct } . \bigcup_{m=1}^{M_n}\{C_m,m^\star=m\}\subseteq\{\text{there exists a run in which all tests are correct}\}. m = 1 ⋃ M n { C m , m ⋆ = m } ⊆ { there exists a run in which all tests are correct } .
The event on the left requires the specially selected run m ⋆ m^\star m ⋆ to be correct and is therefore sufficient, but not necessary, for the existence of a correct run.
(b). Let
F n : = { max m ≤ M n , l ∈ T ∣ U ^ l [ m ] ∣ ≤ ω n } , F_n := \left\{\max_{m\le M_n,l\in\mathcal{T}}|\widehat{U}^{[m]}_l|\le\omega_n\right\}, F n := { m ≤ M n , l ∈ T max ∣ U l [ m ] ∣ ≤ ω n } ,
so that P ( F n ∣ D ) = 1 − δ n \mathbb{P}(F_n\mid\mathcal{D})=1-\delta_n P ( F n ∣ D ) = 1 − δ n . On E n ∩ F n E_n\cap F_n E n ∩ F n , every null statistic is at most z + ω n < t n z+\omega_n<t_n z + ω n < t n , and every nonnull statistic is at least κ min , n − z − ω n > t n \kappa_{\min,n}-z-\omega_n>t_n κ m i n , n − z − ω n > t n , for all large $n. Every run is then correct, so G ^ n = { G ⋆ } \widehat{\mathcal{G}}_n=\{\mathcal{G}^\star\} G n = { G ⋆ } with probability at least ( 1 − δ n ) P ( E n ) (1-\delta_n)\mathbb{P}(E_n) ( 1 − δ n ) P ( E n ) .
Appendix C. Proofs for Section 5
Let Δ = Skel ( G s ) △ Skel ( G t ) \Delta=\operatorname{Skel}(\mathcal{G}_s)\triangle\operatorname{Skel}(\mathcal{G}_t) Δ = Skel ( G s ) △ Skel ( G t ) for brevity. We use three standard facts.
Fact 1. For CPDAGs G \mathcal{G} G and G ′ \mathcal{G}' G ′ , G ≺ G ′ \mathcal{G}\prec\mathcal{G}' G ≺ G ′ exactly when there are DAGs D \mathcal{D} D and D ′ = D + e \mathcal{D}'=\mathcal{D}+e D ′ = D + e in their classes [6 ] . Here D + e \mathcal{D}+e D + e is D \mathcal{D} D with one added edge on the pair e e e .
Fact 2. For CPDAGs G \mathcal{G} G and H \mathcal{H} H , H ⪯ G \mathcal{H}\preceq\mathcal{G} H ⪯ G exactly when every conditional independence encoded by G \mathcal{G} G is encoded by H \mathcal{H} H (Proposition 1). In particular, Skel ( H ) ⊆ Skel ( G ) \operatorname{Skel}(\mathcal{H})\subseteq\operatorname{Skel}(\mathcal{G}) Skel ( H ) ⊆ Skel ( G ) . Indeed, if { u , v } ∉ Skel ( G ) \{u,v\}\notin\operatorname{Skel}(\mathcal{G}) { u , v } ∈ / Skel ( G ) , then u u u and v v v are d-separated in G \mathcal{G} G by some set. The CPDAG H \mathcal{H} H encodes the same independence, so u u u and v v v are nonadjacent in H \mathcal{H} H .
Fact 3. A subgraph of a DAG encodes every independence of the DAG. By Fact 2, the class of the subgraph therefore precedes the class of the DAG. To see the first claim, let D ′ \mathcal{D}' D ′ be a subgraph of a DAG D \mathcal{D} D . Every path of D ′ \mathcal{D}' D ′ is a path of D \mathcal{D} D with the same colliders. Every descendant of a vertex in D ′ \mathcal{D}' D ′ is a descendant of that vertex in D \mathcal{D} D . Hence a path that d-connects two vertices given a set S S S in D ′ \mathcal{D}' D ′ also d-connects them given S S S in D \mathcal{D} D .
We also pass from paths in L \mathcal{L} L to sequences of DAGs. Lemma 3, Theorem 3 and Proposition 5 use the following definition and lemma.
Definition 14 (Valid DAG operations). Let D = ( V , E ) \mathcal{D}=(V,E) D = ( V , E ) be a DAG. A valid operation on D \mathcal{D} D yields a new DAG D ′ \mathcal{D}' D ′ via one of three mechanisms: (1) edge addition , where D ′ = ( V , E ∪ { h } ) D'=(V,E\cup\{h\}) D ′ = ( V , E ∪ { h }) , h ∉ E h\notin E h ∈ / E , and D ′ D' D ′ remains acyclic;
(2) edge deletion , where D ′ = ( V , E ∖ { h } ) D'=(V,E\setminus\{h\}) D ′ = ( V , E ∖ { h }) and h ∈ E h\in E h ∈ E ;
(3) covered edge reversal , where D ′ D' D ′ is obtained by reversing a covered edge h = u → v h=u\to v h = u → v in D D D , that is, an edge with
Pa D ( v ) = Pa D ( u ) ∪ { u } . \operatorname{Pa}_{D}(v)=\operatorname{Pa}_{D}(u)\cup\{u\}. Pa D ( v ) = Pa D ( u ) ∪ { u } .
A sequence of DAGs is valid if each graph is obtained from its predecessor by a valid operation.
Lemma 2 (DAG–CPDAG correspondence). Let G 0 , … , G k \mathcal{G}_0,\ldots,\mathcal{G}_k G 0 , … , G k be a path in L \mathcal{L} L . There exists a valid sequence of DAGs D 0 , … , D m D_0,\ldots,D_m D 0 , … , D m (where m ≥ k m\ge k m ≥ k ) such that D 0 ∈ [ G 0 ] D_0\in[\mathcal{G}_0] D 0 ∈ [ G 0 ] , D m ∈ [ G k ] D_m\in[\mathcal{G}_k] D m ∈ [ G k ] , and every transition D j → D j + 1 D_j\to D_{j+1} D j → D j + 1 is either a single edge addition, a single edge deletion, or a covered edge reversal. The sequence can be chosen so that exactly k k k transitions are edge additions or deletions, and so that the classes of D 0 , … , D m D_0,\ldots,D_m D 0 , … , D m , with consecutive repetitions removed, are G 0 , … , G k \mathcal{G}_0,\ldots,\mathcal{G}_k G 0 , … , G k in this order. Such a sequence represents the path. Conversely, let D 0 , … , D m D_0,\ldots,D_m D 0 , … , D m be any valid sequence of DAGs with exactly r r r edge additions and deletions. Then the classes of D 0 , … , D m D_0,\ldots,D_m D 0 , … , D m , with consecutive repetitions removed, form a path in L \mathcal{L} L with r r r steps.
Proof. We construct the sequence inductively, starting from any DAG D 0 ∈ [ G 0 ] D_0\in[\mathcal{G}_0] D 0 ∈ [ G 0 ] . Let D c u r r D_{\mathrm{curr}} D curr be the current DAG representative of G i \mathcal{G}_i G i . Consider a step G i → G i + 1 \mathcal{G}_i\to\mathcal{G}_{i+1} G i → G i + 1 in the path. By Fact 1, there exist representatives D ∈ [ G i ] D\in[\mathcal{G}_i] D ∈ [ G i ] and D ′ ∈ [ G i + 1 ] D'\in[\mathcal{G}_{i+1}] D ′ ∈ [ G i + 1 ] such that D ′ D' D ′ is obtained from D D D by adding or deleting a single edge [6 ] . Since D c u r r D_{\mathrm{curr}} D curr and D D D belong to the same equivalence class [ G i ] [\mathcal{G}_i] [ G i ] , there exists a sequence of covered edge reversals transforming D c u r r D_{\mathrm{curr}} D curr to D D D [5 ] . We append this sequence to the DAG sequence, followed by the single operation transforming D D D to D ′ D' D ′ . We repeat this construction for all steps in the CPDAG path. Every DAG reached by the covered edge reversals stays in [ G i ] [\mathcal{G}_i] [ G i ] [5 ] . The step G i → G i + 1 \mathcal{G}_i\to\mathcal{G}_{i+1} G i → G i + 1 therefore contributes exactly one edge addition or deletion, and this operation leads from [ G i ] [\mathcal{G}_i] [ G i ] to [ G i + 1 ] [\mathcal{G}_{i+1}] [ G i + 1 ] . Hence the constructed sequence represents the path.
For the converse, a covered edge reversal preserves the class [5 ] . By Fact 1, an edge addition or deletion moves to a neighboring class. The classes of the sequence, with consecutive repetitions removed, therefore form a path with one step per edge addition or deletion. □
Bounds for common lower and upper graphs
C.1. Bounds for common lower and upper graphs. We prove Propositions 2 and 3 for a finite collection A \mathcal{A} A of CPDAGs, as extended at the end of § 5.1 . The pair ( G s , G t ) (\mathcal{G}_s,\mathcal{G}_t) ( G s , G t ) is the case A = { G s , G t } \mathcal{A}=\{\mathcal{G}_s,\mathcal{G}_t\} A = { G s , G t } .
Proof of Proposition 2. Lower bound. The DAG D ∩ ( A ) \mathcal{D}_{\cap}(\mathcal{A}) D ∩ ( A ) is a subgraph of the chosen DAG representative D G \mathcal{D}_{\mathcal{G}} D G of every G ∈ A \mathcal{G}\in\mathcal{A} G ∈ A . By Fact 3, the CPDAG of D ∩ ( A ) \mathcal{D}_{\cap}(\mathcal{A}) D ∩ ( A ) is a common lower graph, of rank ∣ E ( D ∩ ( A ) ) ∣ |E(\mathcal{D}_{\cap}(\mathcal{A}))| ∣ E ( D ∩ ( A )) ∣ .
Upper bound. Let H \mathcal{H} H be any common lower graph. By Fact 2, Skel ( H ) ⊆ Skel ( G ) \operatorname{Skel}(\mathcal{H})\subseteq\operatorname{Skel}(\mathcal{G}) Skel ( H ) ⊆ Skel ( G ) for every G ∈ A \mathcal{G}\in\mathcal{A} G ∈ A , so the skeleton of H \mathcal{H} H lies in Skel ∩ ( A ) \operatorname{Skel}_{\cap}(\mathcal{A}) Skel ∩ ( A ) . Let { u , w } \{u,w\} { u , w } and { v , w } \{v,w\} { v , w } be adjacent in Γ L ( A ) \Gamma_{\mathord{\mathrm{L}}}(\mathcal{A}) Γ L ( A ) . Then ( u , w , v ) (u,w,v) ( u , w , v ) is a forbidden triple for A \mathcal{A} A , with u → w ← v u\to w\leftarrow v u → w ← v a v-structure in G 1 ∈ A \mathcal{G}_1\in\mathcal{A} G 1 ∈ A but not in G 2 ∉ A \mathcal{G}_2\notin\mathcal{A} G 2 ∈ / A . Let D 1 \mathcal{D}_1 D 1 be a DAG in the class of G 1 \mathcal{G}_1 G 1 . In D 1 \mathcal{D}_1 D 1 , the vertices u u u and v v v are nonadjacent and w w w is a child of both. One of u u u and v v v is not a descendant of the other; say v v v is not a descendant of u u u . In G 2 \mathcal{G}_2 G 2 , the triple is unshielded and not a v-structure. Hence
u and v are d-separated in G 1 by Pa D 1 ( u ) , a set that does not contain w ; u\text{ and }v\text{ are d-separated in }\mathcal{G}_1\text{ by }\operatorname{Pa}_{D_1}(u),\text{ a set that does not contain }w; u and v are d-separated in G 1 by Pa D 1 ( u ) , a set that does not contain w ;
u and v are d-separated in G 2 by some set, and every such set contains w . u\text{ and }v\text{ are d-separated in }\mathcal{G}_2\text{ by some set, and every such set contains }w. u and v are d-separated in G 2 by some set, and every such set contains w .
By Fact 2, both independences are encoded by H \mathcal{H} H . The pair { u , v } \{u,v\} { u , v } is absent from H \mathcal{H} H , since { u , v } \{u,v\} { u , v } lies in no skeleton of A \mathcal{A} A . Suppose H \mathcal{H} H kept both legs. If the triple were not a v-structure of H \mathcal{H} H , then H \mathcal{H} H would violate the first independence. If the triple were a v-structure of H \mathcal{H} H , then H \mathcal{H} H would violate the second independence. Hence H \mathcal{H} H omits { u , w } \{u,w\} { u , w } or { v , w } \{v,w\} { v , w } .
Vertex cover. The edge of Γ L ( A ) \Gamma_{\mathord{\mathrm{L}}}(\mathcal{A}) Γ L ( A ) between { u , w } \{u,w\} { u , w } and { v , w } \{v,w\} { v , w } was arbitrary. The edges of Skel ∩ ( A ) \operatorname{Skel}_{\cap}(\mathcal{A}) Skel ∩ ( A ) missing from H \mathcal{H} H therefore form a vertex cover of Γ L ( A ) \Gamma_{\mathord{\mathrm{L}}}(\mathcal{A}) Γ L ( A ) . Since rank ( H ) = ∣ Skel ( H ) ∣ \operatorname{rank}(\mathcal{H})=|\operatorname{Skel}(\mathcal{H})| rank ( H ) = ∣ Skel ( H ) ∣ ,
rank ( H ) ≤ ∣ Skel ∩ ( A ) ∣ − τ ( Γ L ( A ) ) . \operatorname{rank}(\mathcal{H})\leq|\operatorname{Skel}_{\cap}(\mathcal{A})|-\tau(\Gamma_{\mathord{\mathrm{L}}}(\mathcal{A})). rank ( H ) ≤ ∣ Skel ∩ ( A ) ∣ − τ ( Γ L ( A )) .
Finally, τ ( Γ L ( A ) ) ≥ ν ( Γ L ( A ) ) \tau(\Gamma_{\mathord{\mathrm{L}}}(\mathcal{A}))\geq\nu(\Gamma_{\mathord{\mathrm{L}}}(\mathcal{A})) τ ( Γ L ( A )) ≥ ν ( Γ L ( A )) , since a vertex cover contains an endpoint of each edge of a matching, and these endpoints are distinct. □
Proof of Proposition 3. By Fact 2, a common upper graph contains every skeleton. Its rank is therefore at least ∣ Skel ∪ ( A ) ∣ |\operatorname{Skel}_{\cup}(\mathcal{A})| ∣ Skel ∪ ( A ) ∣ .
Write H : = G c h ( A ) \mathcal{H}:=\mathcal{G}_{\mathrm{ch}}(\mathcal{A}) H := G ch ( A ) . Since H \mathcal{H} H is chordal, H \mathcal{H} H is a CPDAG. The conditional independences encoded by H \mathcal{H} H are exactly its graph separations [30 ] . Let G ∈ A \mathcal{G} \in\mathcal{A} G ∈ A . By construction, moral ( G ) \operatorname{moral}(\mathcal{G}) moral ( G ) is a subgraph of H \mathcal{H} H . Every separation in H \mathcal{H} H is therefore a separation in moral ( G ) \operatorname{moral}(\mathcal{G}) moral ( G ) , hence a d-separation in G \mathcal{G} G [30 ] . By Fact 2, G ⪯ H \mathcal{G} \preceq\mathcal{H} G ⪯ H . Thus H \mathcal{H} H is a common upper graph, giving
ρ U ( A ) ≤ rank ( H ) = ∣ E ( H ) ∣ . \rho_U(\mathcal{A}) \le\operatorname{rank}(\mathcal{H}) = \lvert E(\mathcal{H})\rvert. ρ U ( A ) ≤ rank ( H ) = ∣ E ( H )∣ .
Lower bounds from mismatches
Proof of Theorem 5. Let P P P be a shortest path from G s G_s G s to G t G_t G t , so that d ( G s , G t ) d(G_s,G_t) d ( G s , G t ) is the number of steps of P P P . By Fact 1, each step adds or deletes the edge on one pair of vertices. A step that deletes a pair of Skel ( G t ) \operatorname{Skel}(G_t) Skel ( G t ) performs ER on that pair. A step that adds a pair outside Skel ( G t ) \operatorname{Skel}(G_t) Skel ( G t ) performs EA on that pair. These are the detour steps of P P P . Let F F F be the set of distinct detour operations performed along P P P .
By Definition 13, P P P performs an operation of every M ∈ M M \in\mathcal{M} M ∈ M . So F ∩ ⋃ M ∈ M M F \cap\bigcup_{M \in\mathcal{M}} M F ∩ ⋃ M ∈ M M meets every member of M \mathcal{M} M , and is a hitting set for M \mathcal{M} M . By the definition of m ~ o p \widetilde{m}_{\mathrm{op}} m op ,
∣ F ∣ ≥ ∣ F ∩ ⋃ M ∈ M M ∣ ≥ m ~ o p ( M ) . \lvert F\rvert\ge\left\lvert F \cap\bigcup_{M \in\mathcal{M}} M\right\rvert\ge\widetilde{m}_{\mathrm{op}}(\mathcal{M}). ∣ F ∣ ≥ F ∩ M ∈ M ⋃ M ≥ m op ( M ) .
We now count the steps of P P P . Fix a pair e e e and follow the state of e e e along P P P . Each step on e e e switches the state. The steps on e e e therefore alternate between moving e e e away from its state in G t G_t G t and moving e e e back. If e ∉ Δ e \notin\Delta e ∈ / Δ , the state of e e e starts and ends in its target state. The steps on e e e then come in pairs: a detour step, then a step that undoes the detour step. If e ∈ Δ e \in\Delta e ∈ Δ , the first step on e e e moves e e e to its target state, and the remaining steps on $e come in such pairs. Hence
(number of steps on e ) = 1 { e ∈ Δ } + 2 (number of detour steps on e ) . \text{(number of steps on }e\text{)} = \mathbf{1}\{e \in\Delta\} + 2\text{ (number of detour steps on }e\text{)}. (number of steps on e ) = 1 { e ∈ Δ } + 2 (number of detour steps on e ) .
Summing over all pairs gives Equation (6) for P P P , where q ( P ) q(P) q ( P ) is the number of detour steps of P P P , counted with repetition. The count uses no property of P P P other than its endpoints, so Equation (6) holds for every path from G s G_s G s to G t G_t G t . Each operation in F F F is performed at least once, so q ( P ) ≥ ∣ F ∣ q(P) \ge\lvert F\rvert q ( P ) ≥ ∣ F ∣ . Combining these facts with the hitting-set bound gives
d ( G s , G t ) = ∣ Δ ∣ + 2 q ( P ) ≥ ∣ Δ ∣ + 2 ∣ F ∣ ≥ ∣ Δ ∣ + 2 m ~ o p ( M ) . d(G_s,G_t) = \lvert\Delta\rvert+ 2q(P) \ge\lvert\Delta\rvert+ 2\lvert F\rvert\ge\lvert\Delta\rvert+ 2\widetilde{m}_{\mathrm{op}}(\mathcal{M}). d ( G s , G t ) = ∣ Δ ∣ + 2 q ( P ) ≥ ∣ Δ ∣ + 2 ∣ F ∣ ≥ ∣ Δ ∣ + 2 m op ( M ) .
Proof of Corollary 2. Let H H H be a hitting set for I I I . Then H H H contains an operation from each mismatch in I I I . The mismatches in I I I are pairwise disjoint, so these operations are distinct. Hence ∣ H ∣ ≥ ∣ I ∣ \lvert H\rvert\ge\lvert I\rvert ∣ H ∣ ≥ ∣ I ∣ , and m ~ o p ( I ) ≥ ∣ I ∣ \widetilde{m}_{\mathrm{op}}(I) \ge\lvert I\rvert m op ( I ) ≥ ∣ I ∣ . Theorem 5 with M = I \mathcal{M} = I M = I gives d ( G s , G t ) ≥ ∣ Δ ∣ + 2 ∣ I ∣ d(G_s,G_t) \ge\lvert\Delta\rvert+ 2\lvert I\rvert d ( G s , G t ) ≥ ∣ Δ ∣ + 2 ∣ I ∣ . □
The next two lemmas concern a single forbidden triple. The proof of Theorem 4 and Appendix D.§ 2 use Lemma 4.
Lemma 3. Let T = { u , v , w } T = \{u,v,w\} T = { u , v , w } be a triple with { u , w } , { v , w } ∈ Skel ( G s ) ∩ Skel ( G t ) \{u,w\}, \{v,w\} \in\operatorname{Skel}(G_s) \cap\operatorname{Skel}(G_t) { u , w } , { v , w } ∈ Skel ( G s ) ∩ Skel ( G t ) and { u , v } ∉ Skel ( G s ) ∪ Skel ( G t ) \{u,v\} \notin\operatorname{Skel}(G_s) \cup\operatorname{Skel}(G_t) { u , v } ∈ / Skel ( G s ) ∪ Skel ( G t ) . If T T T forms a v v v -structure u → w ← v u \to w \leftarrow v u → w ← v in G s G_s G s but not in G t G_t G t , then any path from G s G_s G s to G t G_t G t in L \mathcal{L} L contains a graph whose skeleton on T T T differs from that of G s G_s G s and G t G_t G t .
Proof. Assume for contradiction that a path exists on which the skeleton on T T T remains exactly { { u , w } , { v , w } } \{\{u,w\},\{v,w\}\} {{ u , w } , { v , w }} . By Lemma 2, a valid sequence of DAGs represents this path, from a DAG D s D_s D s in the class of G s G_s G s to a DAG D t D_t D t in the class of G t G_t G t . Every DAG of the sequence lies in the class of a graph on the path. Since the skeleton on T T T is constant along the path, no edge addition or deletion occurs within T T T . The edges between u u u and w w w and between v v v and w w w can therefore change orientation only by covered edge reversals.
Let D D D be a DAG of the sequence that contains the v-structure u → w ← v u \to w \leftarrow v u → w ← v . The edge u → w u \to w u → w is reversible only if u → w u \to w u → w is covered, that is,
Pa D ( w ) = Pa D ( u ) ∪ { u } . \operatorname{Pa}_D(w) = \operatorname{Pa}_D(u) \cup\{u\}. Pa D ( w ) = Pa D ( u ) ∪ { u } .
However, v ∈ Pa D ( w ) v \in\operatorname{Pa}_D(w) v ∈ Pa D ( w ) , so the covering condition requires v ∈ Pa D ( u ) ∪ { u } v \in\operatorname{Pa}_D(u) \cup\{u\} v ∈ Pa D ( u ) ∪ { u } . Since u ≠ v u \ne v u = v , the covering condition requires v ∈ Pa D ( u ) v \in\operatorname{Pa}_D(u) v ∈ Pa D ( u ) . Thus reversing u → w u \to w u → w requires the edge v → u v \to u v → u . Similarly, reversing v → w v \to w v → w requires the edge u → v u \to v u → v .
In both cases, the reversal is valid only if the shielding edge between u u u and v v v exists. However, { u , v } \{u,v\} { u , v } is in neither skeleton, and by assumption the skeleton on T T T is constant along the path. So { u , v } \{u,v\} { u , v } is absent throughout. Neither leg of the v-structure is ever covered. The sequence therefore keeps u → w ← v u \to w \leftarrow v u → w ← v and cannot reach the non-v-structure of G t G_t G t , a contradiction.
Lemma 4 (Forbidden-triple mismatches). Let ( u , w , v ) ∈ S ( G s , G t ) (u,w,v) \in\mathcal{S}(G_s,G_t) ( u , w , v ) ∈ S ( G s , G t ) . Then the set M ( u , w , v ) M_{(u,w,v)} M ( u , w , v ) of (7) is a mismatch for ( G s , G t ) (G_s,G_t) ( G s , G t ) .
Proof. Write T = { u , v , w } T = \{u,v,w\} T = { u , v , w } . By the definition of S ( G s , G t ) \mathcal{S}(G_s,G_t) S ( G s , G t ) , the legs { u , w } \{u,w\} { u , w } and { v , w } \{v,w\} { v , w } lie in both skeletons, the shield { u , v } \{u,v\} { u , v } lies in neither skeleton, and u → w ← v u \to w \leftarrow v u → w ← v is a v-structure in exactly one of G s G_s G s and G t G_t G t . Let P P P be a path from G s G_s G s to G t G_t G t .
If u → w ← v u \to w \leftarrow v u → w ← v is a v-structure in G s G_s G s , apply Lemma 3 to P P P . Otherwise u → w ← v u \to w \leftarrow v u → w ← v is a v-structure in G t G_t G t . The reverse of P P P is a path from G t G_t G t to G s G_s G s , and Lemma 3 applies to the reverse of P P P with the roles of G s G_s G s and G t G_t G t exchanged. In both cases, some graph on P P P has a skeleton on T T T other than { { u , w } , { v , w } } \{\{u,w\},\{v,w\}\} {{ u , w } , { v , w }} .
The skeleton of G s G_s G s on T T T is { { u , w } , { v , w } } \{\{u,w\},\{v,w\}\} {{ u , w } , { v , w }} . Consider the first step of P P P that changes the skeleton on T T T . This step deletes a leg or adds the shield. Both legs lie in Skel ( G t ) \operatorname{Skel}(G_t) Skel ( G t ) , and the shield does not. The step therefore performs ER ( u , w ) \operatorname{ER}(u,w) ER ( u , w ) , ER ( w , v ) \operatorname{ER}(w,v) ER ( w , v ) or EA ( u , v ) \operatorname{EA}(u,v) EA ( u , v ) , which is an operation of M ( u , w , v ) M_{(u,w,v)} M ( u , w , v ) . Since P P P was arbitrary, M ( u , w , v ) M_{(u,w,v)} M ( u , w , v ) is a mismatch for ( G s , G t ) (G_s,G_t) ( G s , G t ) .
Decomposition over disconnected blocks
The proof uses Definition 14 and Lemma 2, stated at the start of Appendix C.
Proof of Theorem 3. Call an edge cross if its vertices lie in different blocks. We first show that no graph on a shortest path has a cross edge. Suppose that some graph on a shortest path P P P from G s G_s G s to G t G_t G t has a cross edge. By Lemma 2, there exists a valid sequence of DAGs D 0 , … , D m D_0,\ldots,D_m D 0 , … , D m representing P P P . We construct a new sequence D ~ 0 , … , D ~ m \widetilde{D}_0,\ldots,\widetilde{D}_m D 0 , … , D m , where
D ~ j : = D j with its cross edges removed. \widetilde{D}_j := D_j \text{ with its cross edges removed.} D j := D j with its cross edges removed.
Operations on cross pairs are omitted, and every other operation remains valid:
A deleted edge inside a block is an edge of D ~ j \widetilde{D}_j D j .
An edge that can be added to D j D_j D j without creating a cycle can be added to its subgraph D ~ j \widetilde{D}_j D j .
Let a → b a \to b a → b be a covered edge of D j D_j D j with a , b ∈ V i a,b \in V_i a , b ∈ V i . Then Pa D j ( b ) = Pa D j ( a ) ∪ { a } \operatorname{Pa}_{D_j}(b) = \operatorname{Pa}_{D_j}(a) \cup\{a\} Pa D j ( b ) = Pa D j ( a ) ∪ { a } . Removing cross edges intersects both parent sets with V i V_i V i . Since a ∈ V i a \in V_i a ∈ V i , we obtain
Pa D ~ j ( b ) = Pa D ~ j ( a ) ∪ { a } . \operatorname{Pa}_{\widetilde{D}_j}(b) = \operatorname{Pa}_{\widetilde{D}_j}(a) \cup\{a\}. Pa D j ( b ) = Pa D j ( a ) ∪ { a } .
Hence a → b a \to b a → b remains covered in D ~ j \widetilde{D}_j D j .
Since G s G_s G s and G t G_t G t have no cross edges, D ~ 0 = D 0 \widetilde{D}_0 = D_0 D 0 = D 0 and D ~ m = D m \widetilde{D}_m = D_m D m = D m . After repeated DAGs are dropped, the new sequence is valid. By the converse part of Lemma 2, the classes of the new sequence form a path from G s G_s G s to G t G_t G t with one step per edge addition or deletion. The sequence D 0 , … , D m D_0,\ldots,D_m D 0 , … , D m has one edge addition or deletion per step of P P P . The path P P P adds a cross edge. The cross edge is in neither skeleton, so P P P later removes the cross edge. Both operations are omitted, so the new path is shorter than P P P , a contradiction.
We now compute the distance. Write d i = d V ( G s ∣ V i , G t ∣ V i ) d_i = d_{\mathcal{V}}(G_s|_{V_i},G_t|_{V_i}) d i = d V ( G s ∣ V i , G t ∣ V i ) . A CPDAG without cross edges is the class of a disjoint union of DAGs over the blocks. This class depends only on the classes of the parts, since its skeleton and v-structures are those of the parts. By Fact 1, a step between two such CPDAGs is realized by DAGs D \mathcal{D} D and D + e \mathcal{D}+e D + e with e e e inside a single block V i V_i V i . The step therefore moves the restriction to V i V_i V i to a neighbor over V i V_i V i and leaves the other restrictions unchanged. By the first part, no graph on a shortest path has a cross edge. Along a shortest path, the restrictions to V i V_i V i , with repetitions removed, therefore form a path from G s ∣ V i G_s|_{V_i} G s ∣ V i to G t ∣ V i G_t|_{V_i} G t ∣ V i whose steps are the steps inside V i V_i V i . This path has at least d i d_i d i steps, so
d ( G s , G t ) = ∑ i ( number of steps inside V i ) ≥ ∑ i d i . d(G_s,G_t) = \sum_i (\text{number of steps inside } V_i) \geq\sum_i d_i. d ( G s , G t ) = i ∑ ( number of steps inside V i ) ≥ i ∑ d i .
Conversely, a step between neighbors over V i V_i V i , realized by adding an edge to a DAG over V i V_i V i , remains a step between neighbors over V V V when the DAGs over the other blocks are kept fixed. Concatenating shortest paths over the blocks therefore gives a path of length ∑ i d i \sum_i d_i ∑ i d i . Hence d ( G s , G t ) = ∑ i d i d(G_s,G_t) = \sum_i d_i d ( G s , G t ) = ∑ i d i . Since each block needs at least d i d_i d i steps, a shortest path makes exactly d i d_i d i steps inside each V i V_i V i .
Polytree shortest path
We first fix notation for Lemma 5. We identify the triples ( u , w , v ) (u,w,v) ( u , w , v ) and ( v , w , u ) (v,w,u) ( v , w , u ) . The three vertices of a triple are distinct, since its legs { u , w } \{u,w\} { u , w } and { w , v } \{w,v\} { w , v } and its shield { u , v } \{u,v\} { u , v } are pairs of distinct vertices. For a forbidden triple T = ( u , w , v ) T=(u,w,v) T = ( u , w , v ) , write M T = M ( u , w , v ) M_T=M_{(u,w,v)} M T = M ( u , w , v ) . By (7) ,
M T = { ER ( u , w ) , ER ( w , v ) , EA ( u , v ) } . M_T=\{\operatorname{ER}(u,w),\operatorname{ER}(w,v),\operatorname{EA}(u,v)\}. M T = { ER ( u , w ) , ER ( w , v ) , EA ( u , v )} .
Thus M T M_T M T contains exactly two edge removals, one on each leg of T T T , and exactly one edge addition, on the shield of T T T . As in the definition of m ~ o p \widetilde{m}_{\mathrm{op}} m op before Theorem 5, a hitting set for a collection M \mathcal{M} M of mismatches is a set H H H such that
H ⊆ ⋃ M ∈ M M and H ∩ M ≠ ∅ for every M ∈ M . H\subseteq\bigcup_{M\in\mathcal{M}}M
\quad\text{and}\quad
H\cap M\ne\varnothing\quad\text{for every }M\in\mathcal{M}. H ⊆ M ∈ M ⋃ M and H ∩ M = ∅ for every M ∈ M .
A hitting set with m ~ o p ( M ) \widetilde{m}_{\mathrm{op}}(\mathcal{M}) m op ( M ) elements is minimum.
Lemma 5. Let G s G_s G s and G t G_t G t be CPDAGs where at least one of them is a polytree. Let S = S ( G s , G t ) S=\mathcal{S}(G_s,G_t) S = S ( G s , G t ) be the set of forbidden triples, and let M S = { M ( u , w , v ) : ( u , w , v ) ∈ S } \mathcal{M}_S=\{M_{(u,w,v)}:(u,w,v)\in S\} M S = { M ( u , w , v ) : ( u , w , v ) ∈ S } be the collection of forbidden-triple mismatches. Then some minimum hitting set for M S \mathcal{M}_S M S , of size m ~ o p ( M S ) \widetilde{m}_{\mathrm{op}}(\mathcal{M}_S) m op ( M S ) , consists entirely of edge removal (ER) operations.
Proof. Fix a pair { u , v } \{u,v\} { u , v } . By the form of M T M_T M T , the operation EA ( u , v ) \operatorname{EA}(u,v) EA ( u , v ) lies in M T M_T M T if and only if { u , v } \{u,v\} { u , v } is the shield of T T T , that is, T = ( u , x , v ) T=(u,x,v) T = ( u , x , v ) for some vertex x x x . We show that at most one triple in S S S has shield { u , v } \{u,v\} { u , v } . Suppose that T 1 = ( u , w 1 , v ) T_1=(u,w_1,v) T 1 = ( u , w 1 , v ) and T 2 = ( u , w 2 , v ) T_2=(u,w_2,v) T 2 = ( u , w 2 , v ) are distinct triples in S S S , so that w 1 ≠ w 2 w_1\ne w_2 w 1 = w 2 . By the definition of S S S , the legs of T 1 T_1 T 1 and T 2 T_2 T 2 lie in both skeletons:
{ u , w 1 } , { w 1 , v } , { v , w 2 } , { w 2 , u } ∈ Skel ( G s ) ∩ Skel ( G t ) . \{u,w_1\},\{w_1,v\},\{v,w_2\},\{w_2,u\}\in\operatorname{Skel}(G_s)\cap\operatorname{Skel}(G_t). { u , w 1 } , { w 1 , v } , { v , w 2 } , { w 2 , u } ∈ Skel ( G s ) ∩ Skel ( G t ) .
The vertices u u u , w 1 w_1 w 1 , v v v and w 2 w_2 w 2 are distinct, because w 1 ≠ w 2 w_1\ne w_2 w 1 = w 2 and the vertices of each triple are distinct. Hence u − w 1 − v − w 2 − u u-w_1-v-w_2-u u − w 1 − v − w 2 − u is a cycle of length four in Skel ( G s ) \operatorname{Skel}(G_s) Skel ( G s ) and in Skel ( G t ) \operatorname{Skel}(G_t) Skel ( G t ) . The cycle contradicts the assumption that the skeleton of G s G_s G s or of G t G_t G t has no cycles. Therefore at most one triple in S S S has shield { u , v } \{u,v\} { u , v } , and
∣ { M ∈ M S : EA ( u , v ) ∈ M } ∣ ≤ 1. \left|\{M\in\mathcal{M}_S:\operatorname{EA}(u,v)\in M\}\right|\le1. ∣ { M ∈ M S : EA ( u , v ) ∈ M } ∣ ≤ 1.
The pair { u , v } \{u,v\} { u , v } was arbitrary, so this bound holds for every pair.
Now let H H H be a minimum hitting set for M S \mathcal{M}_S M S that contains an edge addition EA ( u , v ) \operatorname{EA}(u,v) EA ( u , v ) . Since H ⊆ ⋃ M ∈ M S M H\subseteq\bigcup_{M\in\mathcal{M}_S}M H ⊆ ⋃ M ∈ M S M , the operation EA ( u , v ) \operatorname{EA}(u,v) EA ( u , v ) lies in at least one mismatch of M S \mathcal{M}_S M S . By the bound on the number of mismatches containing EA ( u , v ) \operatorname{EA}(u,v) EA ( u , v ) , the operation EA ( u , v ) \operatorname{EA}(u,v) EA ( u , v ) lies in exactly one mismatch, say M T M_T M T with T = ( u , w , v ) ∈ S T=(u,w,v)\in S T = ( u , w , v ) ∈ S . Define
H ′ : = ( H ∖ { EA ( u , v ) } ) ∪ { ER ( u , w ) } . H' := \left(H\setminus\{\operatorname{EA}(u,v)\}\right)\cup\{\operatorname{ER}(u,w)\}. H ′ := ( H ∖ { EA ( u , v )} ) ∪ { ER ( u , w )} .
We check that H ′ H' H ′ is a hitting set. First, ER ( u , w ) ∈ M T \operatorname{ER}(u,w)\in M_T ER ( u , w ) ∈ M T , so H ′ ⊆ ⋃ M ∈ M S M H'\subseteq\bigcup_{M\in\mathcal{M}_S}M H ′ ⊆ ⋃ M ∈ M S M . Next, let M ∈ M S M\in\mathcal{M}_S M ∈ M S .
If M = M T M=M_T M = M T , then ER ( u , w ) ∈ M ∩ H ′ \operatorname{ER}(u,w)\in M\cap H' ER ( u , w ) ∈ M ∩ H ′ .
If M ≠ M T M\ne M_T M = M T , then EA ( u , v ) ∉ M \operatorname{EA}(u,v)\notin M EA ( u , v ) ∈ / M by the bound on the number of mismatches containing EA ( u , v ) \operatorname{EA}(u,v) EA ( u , v ) . Hence M ∩ H ⊆ H ∖ { EA ( u , v ) } ⊆ H ′ M\cap H\subseteq H\setminus\{\operatorname{EA}(u,v)\}\subseteq H' M ∩ H ⊆ H ∖ { EA ( u , v )} ⊆ H ′ . Since H H H is a hitting set, M ∩ H ′ ⊇ M ∩ H ≠ ∅ M\cap H'\supseteq M\cap H\ne\varnothing M ∩ H ′ ⊇ M ∩ H = ∅ .
Thus H ′ H' H ′ is a hitting set. By construction, ∣ H ′ ∣ ≤ ∣ H ∣ = m ~ o p ( M S ) |H'|\le|H|=\widetilde{m}_{\mathrm{op}}(\mathcal{M}_S) ∣ H ′ ∣ ≤ ∣ H ∣ = m op ( M S ) . No hitting set has fewer than m ~ o p ( M S ) \widetilde{m}_{\mathrm{op}}(\mathcal{M}_S) m op ( M S ) elements, so H ′ H' H ′ is also a minimum hitting set. The edge additions in H ′ H' H ′ are exactly the edge additions in H H H other than EA ( u , v ) \operatorname{EA}(u,v) EA ( u , v ) , because ER ( u , w ) \operatorname{ER}(u,w) ER ( u , w ) is an edge removal. Hence H ′ H' H ′ contains one fewer edge addition than H H H .
The collection M S \mathcal{M}_S M S is finite, so minimum hitting sets exist. Among them, choose H ∗ H^* H ∗ with the fewest edge additions. Suppose H ∗ H^* H ∗ contained an edge addition. The exchange of the previous paragraph, applied with H = H ∗ H=H^* H = H ∗ , would then produce a minimum hitting set with fewer edge additions than H ∗ H^* H ∗ , which contradicts the choice of H ∗ H^* H ∗ . Hence H ∗ H^* H ∗ contains no edge addition. By Definition 12, every detour operation is an edge removal or an edge addition, so H ∗ H^* H ∗ consists entirely of edge removals. □ \square □
For a DAG K K K , write I ( K ) \mathcal{I}(K) I ( K ) for the set of conditional independences encoded by K K K . For two DAGs K K K and L L L , the inclusion I ( K ) ⊆ I ( L ) \mathcal{I}(K)\subseteq\mathcal{I}(L) I ( K ) ⊆ I ( L ) , equivalently [ L ] ⪰ [ K ] [L]\succeq[K] [ L ] ⪰ [ K ] by Fact 2, implies the following basic conditions [27 ] : (a) Skel ( L ) ⊆ Skel ( K ) \operatorname{Skel}(L)\subseteq\operatorname{Skel}(K) Skel ( L ) ⊆ Skel ( K ) ; (b) every v-structure of L L L that is unshielded in K K K is also a v-structure of K K K ; (c) every v-structure of K K K whose legs both lie in Skel ( L ) \operatorname{Skel}(L) Skel ( L ) is also a v-structure of L L L .
The next lemma shows that these conditions are also sufficient for polytrees.
Lemma 6. Let K K K and L L L be DAGs such that their skeletons, Skel ( K ) \operatorname{Skel}(K) Skel ( K ) and Skel ( L ) \operatorname{Skel}(L) Skel ( L ) , are polytrees. Then the basic conditions (a), (b), and (c) hold if and only if I ( K ) ⊆ I ( L ) \mathcal{I}(K) \subseteq\mathcal{I}(L) I ( K ) ⊆ I ( L ) .
Proof. Necessity follows from the result of Kocka et al. [27 ] stated before the lemma.
For sufficiency, suppose that (a), (b), and (c) hold. Construct a DAG J J J by deleting from K K K every edge whose underlying pair is absent from Skel ( L ) \operatorname{Skel}(L) Skel ( L ) , retaining the orientations of all remaining edges. By (a),
Skel ( J ) = Skel ( L ) . \operatorname{Skel}(J) = \operatorname{Skel}(L). Skel ( J ) = Skel ( L ) . We show that J J J and L L L also have the same v-structures.
Suppose first that u → w ← v u \to w \leftarrow v u → w ← v is a v-structure of J J J . Both arrows belong to K K K . Since K K K is a polytree, u u u and v v v cannot be adjacent in K K K , as an edge between u u u and v v v would create a triangle in the skeleton of K K K . Thus u → w ← v u \to w \leftarrow v u → w ← v is also a v-structure of K K K . Both legs lie in Skel ( J ) = Skel ( L ) \operatorname{Skel}(J) = \operatorname{Skel}(L) Skel ( J ) = Skel ( L ) , so condition (c) implies that u → w ← v u \to w \leftarrow v u → w ← v is a v-structure of L L L .
Conversely, suppose that u → w ← v u \to w \leftarrow v u → w ← v is a v-structure of L L L . By (a), both legs belong to Skel ( K ) \operatorname{Skel}(K) Skel ( K ) . Since K K K is a polytree, u u u and v v v are nonadjacent in K K K . Condition (b) therefore implies that u → w ← v u \to w \leftarrow v u → w ← v is a v-structure of K K K . Both arrows are retained in J J J , so u → w ← v u \to w \leftarrow v u → w ← v is also a v-structure of J J J .
Consequently, J J J and L L L have the same skeleton and the same v-structures, and hence are Markov equivalent. Since J J J is obtained from K K K by edge deletions, Fact 3 shows that every conditional independence encoded by K K K is also encoded by J J J . Therefore,
I ( K ) ⊆ I ( J ) = I ( L ) , \mathcal{I}(K) \subseteq\mathcal{I}(J) = \mathcal{I}(L), I ( K ) ⊆ I ( J ) = I ( L ) , which proves sufficiency. □
Proof of Theorem 4. Let M S \mathcal{M}_{S} M S be the collection of forbidden-triple mismatches defined before Theorem 4. The theorem makes three claims. First, some shortest path is a down-up path, so that d ( G s , G t ) = d ↓ ↑ ( G s , G t ) d(G_s, G_t) = d_{\downarrow\uparrow}(G_s, G_t) d ( G s , G t ) = d ↓↑ ( G s , G t ) . Second, d ( G s , G t ) = ∣ Δ ∣ + 2 m ~ o p ( M S ) d(G_s, G_t) = |\Delta| + 2\tilde{m}_{\mathrm{op}}(\mathcal{M}_{S}) d ( G s , G t ) = ∣Δ∣ + 2 m ~ op ( M S ) . Third, the shortest down-up path traverses through polytrees. We first construct a down-up path P ⋆ P^\star P ⋆ of length ∣ Δ ∣ + 2 m ~ o p ( M S ) |\Delta| + 2\tilde{m}_{\mathrm{op}}(\mathcal{M}_{S}) ∣Δ∣ + 2 m ~ op ( M S ) , and then derive the three claims.
By Lemma 5, there is a minimum hitting set H ⋆ H^\star H ⋆ for M S \mathcal{M}_{S} M S that consists entirely of edge removals. Let
E c o n f l i c t : = { { a , b } : ER ( a , b ) ∈ H ⋆ } E_{\mathrm{conflict}} := \{\{a,b\} : \operatorname{ER}(a,b) \in H^\star\} E conflict := {{ a , b } : ER ( a , b ) ∈ H ⋆ }
be the set of pairs removed by the operations in H ⋆ H^\star H ⋆ . Distinct edge removals act on distinct pairs, so ∣ E c o n f l i c t ∣ = ∣ H ⋆ ∣ = m ~ o p ( M S ) |E_{\mathrm{conflict}}| = |H^\star| = \tilde{m}_{\mathrm{op}}(\mathcal{M}_{S}) ∣ E conflict ∣ = ∣ H ⋆ ∣ = m ~ op ( M S ) . Each operation in H ⋆ H^\star H ⋆ lies in some mismatch M ( u , w , v ) \mathcal{M}_{(u,w,v)} M ( u , w , v ) , and the edge removals in M ( u , w , v ) \mathcal{M}_{(u,w,v)} M ( u , w , v ) act on the legs { u , w } \{u,w\} { u , w } and { w , v } \{w,v\} { w , v } . Hence each pair in E c o n f l i c t E_{\mathrm{conflict}} E conflict is a leg of a forbidden triple, and
E c o n f l i c t ⊆ Skel ( G s ) ∩ Skel ( G t ) . E_{\mathrm{conflict}} \subseteq\operatorname{Skel}(G_s) \cap\operatorname{Skel}(G_t). E conflict ⊆ Skel ( G s ) ∩ Skel ( G t ) .
Let D s D_s D s be a DAG in the equivalence class [ G s ] [G_s] [ G s ] . Let D M D_M D M be the subgraph of D s D_s D s obtained by removing the edges on the pairs in
E c o n f l i c t ∪ ( Skel ( G s ) ∖ Skel ( G t ) ) . E_{\mathrm{conflict}} \cup\bigl(\operatorname{Skel}(G_s) \setminus\operatorname{Skel}(G_t)\bigr). E conflict ∪ ( Skel ( G s ) ∖ Skel ( G t ) ) .
Since a subgraph of a DAG is a DAG, let G M G_M G M be the CPDAG representing the equivalence class of D M D_M D M .
We show that G M G_M G M is a common lower bound of G s G_s G s and G t G_t G t :
G M ⪯ G s G_M \preceq G_s G M ⪯ G s : Since D M D_M D M is a subgraph of D s D_s D s , Fact 3 gives G M ⪯ G s G_M \preceq G_s G M ⪯ G s .
G M ⪯ G t G_M \preceq G_t G M ⪯ G t : Apply Lemma 6 with K K K a DAG in the class of G t G_t G t and L = D M L = D_M L = D M . The skeleton Skel ( G t ) \operatorname{Skel}(G_t) Skel ( G t ) is a forest, and Skel ( D M ) ⊆ Skel ( G s ) \operatorname{Skel}(D_M) \subseteq\operatorname{Skel}(G_s) Skel ( D M ) ⊆ Skel ( G s ) has no cycles. By Lemma 6, verifying the basic conditions (a), (b), and (c) suffices: (a) Skel ( G M ) ⊆ Skel ( G t ) \operatorname{Skel}(G_M) \subseteq\operatorname{Skel}(G_t) Skel ( G M ) ⊆ Skel ( G t ) holds by construction, since all edges in Skel ( G s ) ∖ Skel ( G t ) \operatorname{Skel}(G_s) \setminus\operatorname{Skel}(G_t) Skel ( G s ) ∖ Skel ( G t ) were removed. (b) Let u → w ← v u \to w \leftarrow v u → w ← v be a v-structure in G M G_M G M . Both arrows are edges of D s D_s D s , since D M D_M D M is a subgraph of D s D_s D s . The vertices u u u and v v v are nonadjacent in D s D_s D s , since Skel ( G s ) \operatorname{Skel}(G_s) Skel ( G s ) has no cycles. Hence u → w ← v u \to w \leftarrow v u → w ← v is a v-structure in G s G_s G s . Suppose for contradiction that u → w ← v u \to w \leftarrow v u → w ← v is not a v-structure in G t G_t G t . Both legs lie in Skel ( G M ) ⊆ Skel ( G s ) ∩ Skel ( G t ) \operatorname{Skel}(G_M) \subseteq\operatorname{Skel}(G_s) \cap\operatorname{Skel}(G_t) Skel ( G M ) ⊆ Skel ( G s ) ∩ Skel ( G t ) . Since G t G_t G t is a polytree, G t G_t G t has no shielding edge u − v u-v u − v , and neither does G s G_s G s . Hence ( u , w , v ) ∈ S ( G s , G t ) (u,w,v) \in\mathcal{S}(G_s,G_t) ( u , w , v ) ∈ S ( G s , G t ) . However, H ⋆ H^\star H ⋆ hits M ( u , w , v ) \mathcal{M}_{(u,w,v)} M ( u , w , v ) with an edge removal, and that edge removal acts on a leg of ( u , w , v ) (u,w,v) ( u , w , v ) . Hence E c o n f l i c t E_{\mathrm{conflict}} E conflict contains a leg of ( u , w , v ) (u,w,v) ( u , w , v ) , and that leg is absent from G M G_M G M . This missing leg contradicts the presence of the v-structure u → w ← v u \to w \leftarrow v u → w ← v in G M G_M G M . Thus every v-structure in G M G_M G M exists in G t G_t G t . (c) Let u → w ← v u \to w \leftarrow v u → w ← v be a v-structure in G t G_t G t whose legs exist in G M G_M G M . In D M D_M D M , the legs carry the orientations of D s D_s D s , and u u u and v v v are nonadjacent in D s D_s D s . Hence the triple is a v-structure of
G M G_M G M exactly when the triple is a v-structure of G s G_s G s . Suppose G M G_M G M oriented this triple as a non-v-structure. Then G s G_s G s also orients the triple as a non-v-structure. Since G s G_s G s has no cycle to shield u u u and v v v , ( u , w , v ) (u,w,v) ( u , w , v ) would belong to S ( G s , G t ) S(G_s,G_t) S ( G s , G t ) . As in (b), one of its legs would then lie in E c o n f l i c t E_{\mathrm{conflict}} E conflict and would have been deleted. Since both legs remain in G M G_M G M , no conflict exists, and u → w ← v u \to w \leftarrow v u → w ← v is a v-structure of G M G_M G M .
Thus G M ⪯ G t G_M \preceq G_t G M ⪯ G t by Lemma 6.
The skeleton of G M G_M G M is
Skel ( G M ) = ( Skel ( G s ) ∩ Skel ( G t ) ) ∖ E c o n f l i c t . \operatorname{Skel}(G_M) = \left(\operatorname{Skel}(G_s) \cap\operatorname{Skel}(G_t)\right) \setminus E_{\mathrm{conflict}}. Skel ( G M ) = ( Skel ( G s ) ∩ Skel ( G t ) ) ∖ E conflict .
Since E c o n f l i c t ⊆ Skel ( G s ) ∩ Skel ( G t ) E_{\mathrm{conflict}} \subseteq\operatorname{Skel}(G_s) \cap\operatorname{Skel}(G_t) E conflict ⊆ Skel ( G s ) ∩ Skel ( G t ) and ∣ E c o n f l i c t ∣ = m ~ o p ( M s ) \lvert E_{\mathrm{conflict}}\rvert= \widetilde{m}_{\mathrm{op}}(\mathcal{M}_s) ∣ E conflict ∣ = m op ( M s ) ,
rank ( G M ) = ∣ Skel ( G s ) ∩ Skel ( G t ) ∣ − m ~ o p ( M s ) . \operatorname{rank}(G_M) = \lvert\operatorname{Skel}(G_s) \cap\operatorname{Skel}(G_t)\rvert- \widetilde{m}_{\mathrm{op}}(\mathcal{M}_s). rank ( G M ) = ∣ Skel ( G s ) ∩ Skel ( G t )∣ − m op ( M s ) .
The CPDAG poset is graded by rank, and G M G_M G M lies below both G s G_s G s and G t G_t G t . Hence there is a down-up path P ∗ P^* P ∗ that descends from G s G_s G s to G M G_M G M and then ascends from G M G_M G M to G t G_t G t . Each step of P ∗ P^* P ∗ changes the rank by one. Using rank ( G ) = ∣ Skel ( G ) ∣ \operatorname{rank}(G)=\lvert\operatorname{Skel}(G)\rvert rank ( G ) = ∣ Skel ( G )∣ , the length of P ∗ P^* P ∗ is
rank ( G s ) + rank ( G t ) − 2 rank ( G M ) = ∣ Skel ( G s ) ∣ + ∣ Skel ( G t ) ∣ − 2 ∣ Skel ( G s ) ∩ Skel ( G t ) ∣ + 2 m ~ o p ( M s ) = ∣ Δ ∣ + 2 m ~ o p ( M s ) . \begin{aligned}
\operatorname{rank}(G_s) + \operatorname{rank}(G_t) - 2\operatorname{rank}(G_M)
&= \lvert\operatorname{Skel}(G_s)\rvert+ \lvert\operatorname{Skel}(G_t)\rvert- 2\lvert\operatorname{Skel}(G_s) \cap\operatorname{Skel}(G_t)\rvert+ 2\widetilde{m}_{\mathrm{op}}(\mathcal{M}_s) \\
&= \lvert\Delta\rvert+ 2\widetilde{m}_{\mathrm{op}}(\mathcal{M}_s).
\end{aligned} rank ( G s ) + rank ( G t ) − 2 rank ( G M ) = ∣ Skel ( G s )∣ + ∣ Skel ( G t )∣ − 2 ∣ Skel ( G s ) ∩ Skel ( G t )∣ + 2 m op ( M s ) = ∣ Δ ∣ + 2 m op ( M s ) .
The last equality uses ∣ Skel ( G s ) ∣ + ∣ Skel ( G t ) ∣ − 2 ∣ Skel ( G s ) ∩ Skel ( G t ) ∣ = ∣ Δ ∣ \lvert\operatorname{Skel}(G_s)\rvert+ \lvert\operatorname{Skel}(G_t)\rvert- 2\lvert\operatorname{Skel}(G_s) \cap\operatorname{Skel}(G_t)\rvert= \lvert\Delta\rvert ∣ Skel ( G s )∣ + ∣ Skel ( G t )∣ − 2 ∣ Skel ( G s ) ∩ Skel ( G t )∣ = ∣ Δ ∣ .
Every down-up path is a path, so d ( G s , G t ) ≤ d ↓ ↑ ( G s , G t ) d(G_s,G_t) \le d_{\downarrow\uparrow}(G_s,G_t) d ( G s , G t ) ≤ d ↓↑ ( G s , G t ) . The path P ∗ P^* P ∗ is a down-up path, so d ↓ ↑ ( G s , G t ) ≤ ∣ Δ ∣ + 2 m ~ o p ( M s ) d_{\downarrow\uparrow}(G_s,G_t) \le\lvert\Delta\rvert+ 2\widetilde{m}_{\mathrm{op}}(\mathcal{M}_s) d ↓↑ ( G s , G t ) ≤ ∣ Δ ∣ + 2 m op ( M s ) . By Lemma 4, every member of M s \mathcal{M}_s M s is a mismatch for ( G s , G t ) (G_s,G_t) ( G s , G t ) . Theorem 5 with M = M s \mathcal{M}=\mathcal{M}_s M = M s therefore gives ∣ Δ ∣ + 2 m ~ o p ( M s ) ≤ d ( G s , G t ) \lvert\Delta\rvert+ 2\widetilde{m}_{\mathrm{op}}(\mathcal{M}_s) \le d(G_s,G_t) ∣ Δ ∣ + 2 m op ( M s ) ≤ d ( G s , G t ) . Combining the three inequalities gives
∣ Δ ∣ + 2 m ~ o p ( M s ) ≤ d ( G s , G t ) ≤ d ↓ ↑ ( G s , G t ) ≤ ∣ Δ ∣ + 2 m ~ o p ( M s ) . \lvert\Delta\rvert+ 2\widetilde{m}_{\mathrm{op}}(\mathcal{M}_s) \le d(G_s,G_t) \le d_{\downarrow\uparrow}(G_s,G_t) \le\lvert\Delta\rvert+ 2\widetilde{m}_{\mathrm{op}}(\mathcal{M}_s). ∣ Δ ∣ + 2 m op ( M s ) ≤ d ( G s , G t ) ≤ d ↓↑ ( G s , G t ) ≤ ∣ Δ ∣ + 2 m op ( M s ) .
All three inequalities are therefore equalities:
d ( G s , G t ) = d ↓ ↑ ( G s , G t ) = ∣ Δ ∣ + 2 m ~ o p ( M s ) . d(G_s,G_t) = d_{\downarrow\uparrow}(G_s,G_t) = \lvert\Delta\rvert+ 2\widetilde{m}_{\mathrm{op}}(\mathcal{M}_s). d ( G s , G t ) = d ↓↑ ( G s , G t ) = ∣ Δ ∣ + 2 m op ( M s ) .
In particular, the down-up path P ∗ P^* P ∗ is a shortest path. The first two claims follow. Not every shortest path is necessarily a down-up path.
To show every graph on a down-up path from G s G_s G s to G s G_s G s is a polytree, let
G s = G 0 ≻ ⋯ ≻ G i ∗ ≺ ⋯ ≺ G k = G t G_s = G_0 \succ\cdots\succ G_{i^*} \prec\cdots\prec G_k = G_t G s = G 0 ≻ ⋯ ≻ G i ∗ ≺ ⋯ ≺ G k = G t
be any down-up path, for example P ∗ P^* P ∗ . Each covering relation is an instance of ⪯ \preceq ⪯ , and ⪯ \preceq ⪯ is transitive. Hence G i ⪯ G s G_i \preceq G_s G i ⪯ G s for i ≤ i ∗ i \le i^* i ≤ i ∗ , and G i ⪯ G t G_i \preceq G_t G i ⪯ G t for i ≥ i ∗ i \ge i^* i ≥ i ∗ . By Fact 2 at the start of Appendix C, H ⪯ G \mathcal{H} \preceq\mathcal{G} H ⪯ G implies Skel ( H ) ⊆ Skel ( G ) \operatorname{Skel}(\mathcal{H}) \subseteq\operatorname{Skel}(\mathcal{G}) Skel ( H ) ⊆ Skel ( G ) . Therefore
Skel ( G i ) ⊆ Skel ( G s ) for i ≤ i ∗ , Skel ( G i ) ⊆ Skel ( G t ) for i ≥ i ∗ . \operatorname{Skel}(G_i) \subseteq\operatorname{Skel}(G_s) \quad\text{for } i \le i^*, \qquad\operatorname{Skel}(G_i) \subseteq\operatorname{Skel}(G_t) \quad\text{for } i \ge i^*. Skel ( G i ) ⊆ Skel ( G s ) for i ≤ i ∗ , Skel ( G i ) ⊆ Skel ( G t ) for i ≥ i ∗ .
The skeletons of G s G_s G s and G t G_t G t have no cycles, and a subgraph of a graph without cycles has no cycles. Hence every G i G_i G i is a polytree. In particular, the shortest down-up path P ∗ P^* P ∗ traverses through polytrees. □
Appendix D. Proofs for Section 6
Consistency of mismatch heuristic
For the rest of this subsection, fix the target G t G_t G t , and let M ( G ) \mathcal{M}(G) M ( G ) be the collection of all mismatches for ( G , G t ) (G,G_t) ( G , G t ) . Whether a step is a detour depends only on G t G_t G t . A step on the pair e e e is a detour if the step moves e e e away from its state in G t G_t G t . A detour step on e e e performs ER ( e ) \operatorname{ER}(e) ER ( e ) if e ∈ Skel ( G t ) e \in\operatorname{Skel}(G_t) e ∈ Skel ( G t ) and EA ( e ) \operatorname{EA}(e) EA ( e ) otherwise.
Lemma 7. Let G ′ G' G ′ be a neighbor of G G G , let e e e be the pair in which their skeletons differ, and
Δ m ~ o p = m ~ o p ( M ( G ) ) − m ~ o p ( M ( G ′ ) ) . \Delta\widetilde{m}_{\mathrm{op}} = \widetilde{m}_{\mathrm{op}}(\mathcal{M}(G)) - \widetilde{m}_{\mathrm{op}}(\mathcal{M}(G')). Δ m op = m op ( M ( G )) − m op ( M ( G ′ )) . Then
if the step from G G G to G ′ G' G ′ adds e ∉ Skel ( G t ) e \notin\operatorname{Skel}(G_t) e ∈ / Skel ( G t ) , then Δ m ~ o p ≤ 1 \Delta\widetilde{m}_{\mathrm{op}} \le1 Δ m op ≤ 1 ;
if the step deletes e ∈ Skel ( G t ) e \in\operatorname{Skel}(G_t) e ∈ Skel ( G t ) , then Δ m ~ o p ≤ 1 \Delta\widetilde{m}_{\mathrm{op}} \le1 Δ m op ≤ 1 ;
if the step adds e ∈ Skel ( G t ) e \in\operatorname{Skel}(G_t) e ∈ Skel ( G t ) , then Δ m ~ o p ≤ 0 \Delta\widetilde{m}_{\mathrm{op}} \le0 Δ m op ≤ 0 ;
(iv) if the step deletes e ∉ Skel ( G t ) e \notin\operatorname{Skel}(G_t) e ∈ / Skel ( G t ) , then Δ m ~ o p ≤ 0 \Delta\widetilde{m}_{\mathrm{op}} \le0 Δ m op ≤ 0 .
Proof. Let P ′ P' P ′ be a path from G ′ G' G ′ to G t G_t G t . The step from G G G to G ′ G' G ′ followed by P ′ P' P ′ is a path from G G G to G t G_t G t . This path therefore executes an operation of every M ∈ M ( G ) M \in\mathcal{M}(G) M ∈ M ( G ) .
Cases (i) and (ii). The first step of this path performs the detour operation o o o on e e e , namely EA ( e ) \operatorname{EA}(e) EA ( e ) in case (i) and ER ( e ) \operatorname{ER}(e) ER ( e ) in case (ii). If M ∈ M ( G ) M \in\mathcal{M}(G) M ∈ M ( G ) does not contain o o o , then P ′ P' P ′ itself executes an operation of M M M . Since P ′ P' P ′ was arbitrary, M ∈ M ( G ′ ) M \in\mathcal{M}(G') M ∈ M ( G ′ ) . Adding o o o to a minimum hitting set for M ( G ′ ) \mathcal{M}(G') M ( G ′ ) therefore gives a hitting set for M ( G ) \mathcal{M}(G) M ( G ) . Hence m ~ o p ( M ( G ) ) ≤ 1 + m ~ o p ( M ( G ′ ) ) \widetilde{m}_{\mathrm{op}}(\mathcal{M}(G)) \le1 + \widetilde{m}_{\mathrm{op}}(\mathcal{M}(G')) m op ( M ( G )) ≤ 1 + m op ( M ( G ′ )) and Δ m ~ o p ≤ 1 \Delta\widetilde{m}_{\mathrm{op}} \le1 Δ m op ≤ 1 .
Cases (iii) and (iv). The step moves e e e to its state in G t G_t G t , so the first step of this path is not a detour. Hence P ′ P' P ′ itself executes an operation of every M ∈ M ( G ) M \in\mathcal{M}(G) M ∈ M ( G ) , and M ( G ) ⊆ M ( G ′ ) \mathcal{M}(G) \subseteq\mathcal{M}(G') M ( G ) ⊆ M ( G ′ ) . A hitting set for M ( G ′ ) \mathcal{M}(G') M ( G ′ ) also hits every member of M ( G ) \mathcal{M}(G) M ( G ) . Hence m ~ o p ( M ( G ) ) ≤ m ~ o p ( M ( G ′ ) ) \widetilde{m}_{\mathrm{op}}(\mathcal{M}(G)) \le\widetilde{m}_{\mathrm{op}}(\mathcal{M}(G')) m op ( M ( G )) ≤ m op ( M ( G ′ )) and Δ m ~ o p ≤ 0 \Delta\widetilde{m}_{\mathrm{op}} \le0 Δ m op ≤ 0 . □
Proof of Proposition 4. All mismatches. The path of length zero executes no operation, so M ( G t ) = ∅ \mathcal{M}(G_t) = \varnothing M ( G t ) = ∅ . Hence h ( G t ) = 0 h(G_t) = 0 h ( G t ) = 0 . For the distance search, S D ( G ) = N ( G ) S_D(G) = \mathcal{N}(G) S D ( G ) = N ( G ) . We therefore prove h ( G ) − h ( G ′ ) ≤ 1 h(G) - h(G') \le1 h ( G ) − h ( G ′ ) ≤ 1 for neighboring CPDAGs.
Let G ′ G' G ′ be a neighbor of G G G , and let e e e be the pair in which their skeletons differ. Write
Δ s k = ∣ Skel ( G ) △ Skel ( G t ) ∣ − ∣ Skel ( G ′ ) △ Skel ( G t ) ∣ , \Delta_{\mathrm{sk}} = \lvert\operatorname{Skel}(G) \triangle\operatorname{Skel}(G_t) \rvert- \lvert\operatorname{Skel}(G') \triangle\operatorname{Skel}(G_t) \rvert, Δ sk = ∣ Skel ( G ) △ Skel ( G t )∣ − ∣ Skel ( G ′ ) △ Skel ( G t )∣ ,
and let Δ m ~ o p \Delta\widetilde{m}_{\mathrm{op}} Δ m op be as in Lemma 7. Only the status of e e e changes, so Δ s k ∈ { − 1 , 1 } \Delta_{\mathrm{sk}} \in\{-1,1\} Δ sk ∈ { − 1 , 1 } .
If Δ s k = 1 \Delta_{\mathrm{sk}} = 1 Δ sk = 1 , the step adds a pair of Skel ( G t ) \operatorname{Skel}(G_t) Skel ( G t ) or deletes a pair outside that skeleton. Lemma 7(iii)–(iv) gives Δ m ~ o p ≤ 0 \Delta\widetilde{m}_{\mathrm{op}} \le0 Δ m op ≤ 0 , so
h ( G ) − h ( G ′ ) = Δ s k + 2 Δ m ~ o p ≤ 1. h(G) - h(G') = \Delta_{\mathrm{sk}} + 2\Delta\widetilde{m}_{\mathrm{op}} \le1. h ( G ) − h ( G ′ ) = Δ sk + 2Δ m op ≤ 1.
If Δ s k = − 1 \Delta_{\mathrm{sk}} = -1 Δ sk = − 1 , the step deletes a pair of Skel ( G t ) \operatorname{Skel}(G_t) Skel ( G t ) or adds a pair outside that skeleton. Lemma 7(i)–(ii) gives Δ m ~ o p ≤ 1 \Delta\widetilde{m}_{\mathrm{op}} \le1 Δ m op ≤ 1 , so
h ( G ) − h ( G ′ ) = Δ s k + 2 Δ m ~ o p ≤ − 1 + 2 = 1. h(G) - h(G') = \Delta_{\mathrm{sk}} + 2\Delta\widetilde{m}_{\mathrm{op}} \le-1 + 2 = 1. h ( G ) − h ( G ′ ) = Δ sk + 2Δ m op ≤ − 1 + 2 = 1.
Forbidden-triple mismatches. Write
M S ( G ) : = { M T : T ∈ S ( G , G t ) } . \mathcal{M}_{S}(G) := \{M_T : T \in\mathcal{S}(G,G_t)\}. M S ( G ) := { M T : T ∈ S ( G , G t )} .
We show that the four bounds of Lemma 7 also hold with M S \mathcal{M}_{S} M S in place of M \mathcal{M} M . Let G ′ G' G ′ be a neighbor of G G G , with skeletons differing on the pair e e e . By Fact 1, there are DAG representatives D \mathcal{D} D and D ′ \mathcal{D}' D ′ that differ only in the edge on e e e . Fix T = ( u , w , v ) ∈ S ( G , G t ) T = (u,w,v) \in\mathcal{S}(G,G_t) T = ( u , w , v ) ∈ S ( G , G t ) .
If e e e is none of the three pairs of T T T , then D \mathcal{D} D and D ′ \mathcal{D}' D ′ agree on those pairs. The skeleton and v-structure status on T T T are unchanged, so T ∈ S ( G ′ , G t ) T \in\mathcal{S}(G',G_t) T ∈ S ( G ′ , G t ) .
If e e e is a leg of T T T , then e ∈ Skel ( G ) ∩ Skel ( G t ) e \in\operatorname{Skel}(G) \cap\operatorname{Skel}(G_t) e ∈ Skel ( G ) ∩ Skel ( G t ) . The step therefore deletes e e e and falls under Lemma 7(ii). The detour operation ER ( e ) \operatorname{ER}(e) ER ( e ) belongs to M T M_T M T .
If e e e is the shield of T T T , then e ∉ Skel ( G ) ∪ Skel ( G t ) e \notin\operatorname{Skel}(G) \cup\operatorname{Skel}(G_t) e ∈ / Skel ( G ) ∪ Skel ( G t ) . The step therefore adds e e e and falls under Lemma 7(i). The detour operation EA ( e ) \operatorname{EA}(e) EA ( e ) belongs to M T M_T M T .
In cases (i)–(ii) of Lemma 7, every member of M S ( G ) \mathcal{M}_{S}(G) M S ( G ) either contains the detour operation of the step or belongs to M S ( G ′ ) \mathcal{M}_{S}(G') M S ( G ′ ) . In cases (iii)–(iv), M S ( G ) ⊆ M S ( G ′ ) \mathcal{M}_{S}(G) \subseteq\mathcal{M}_{S}(G') M S ( G ) ⊆ M S ( G ′ ) . The hitting-set arguments in the proof of the lemma therefore give the same four bounds for M S \mathcal{M}_{S} M S .
Since S ( G t , G t ) = ∅ \mathcal{S}(G_t,G_t) = \varnothing S ( G t , G t ) = ∅ , the corresponding heuristic also satisfies h ( G t ) = 0 h(G_t) = 0 h ( G t ) = 0 . The preceding two-case calculation then gives h ( G ) − h ( G ′ ) ≤ 1 h(G) - h(G') \le1 h ( G ) − h ( G ′ ) ≤ 1 for neighboring CPDAGs. Thus the forbidden-triple bound of Taeb et al. [53 ] is also consistent.
For either collection, summing the neighboring inequalities along a shortest path from G G G to H \mathcal{H} H gives
h ( G ) ≤ d ( G , H ) + h ( H ) , h(G) \le d(G,\mathcal{H}) + h(\mathcal{H}), h ( G ) ≤ d ( G , H ) + h ( H ) ,
the consistency condition of Hart et al. [20 ] . □
Certification of mismatches
We use the restriction G ∣ W \mathcal{G}|_{W} G ∣ W and the distance d W d_{W} d W of § 5.2 .
Lemma 8 (Restriction). If G \mathcal{G} G and G ′ \mathcal{G}' G ′ are neighbors whose skeletons differ in the pair e e e , then G ∣ W \mathcal{G}|_{W} G ∣ W and G ′ ∣ W \mathcal{G}'|_{W} G ′ ∣ W are neighbors when e ⊆ W e \subseteq W e ⊆ W and are equal otherwise. Hence the operations on pairs inside W W W along any path from G s G_s G s to G t G_t G t form a path from G s ∣ W G_s|_{W} G s ∣ W to G t ∣ W G_t|_{W} G t ∣ W , and there are at least d W ( G s ∣ W , G t ∣ W ) d_W(G_s|_{W},G_t|_{W}) d W ( G s ∣ W , G t ∣ W ) of them.
Proof of Lemma 8. Well defined. Let D \mathcal{D} D and D ′ \mathcal{D}' D ′ be DAGs in the same class. A triple inside W W W is unshielded in the induced subgraph exactly when the triple is unshielded in the DAG. Hence D [ W ] \mathcal{D}[W] D [ W ] and D ′ [ W ] \mathcal{D}'[W] D ′ [ W ] have the same skeleton and the same v-structures, and G ∣ W \mathcal{G}|_W G ∣ W is well defined.
Neighbors. Let G \mathcal{G} G and G ′ \mathcal{G}' G ′ be neighbors, say G ≺ G ′ \mathcal{G} \prec\mathcal{G}' G ≺ G ′ . By Fact 1, there are DAGs D \mathcal{D} D and D ′ = D + e \mathcal{D}' = \mathcal{D} + e D ′ = D + e in their classes. If e ⊈ W e \not\subseteq W e ⊆ W , then D ′ [ W ] = D [ W ] \mathcal{D}'[W] = \mathcal{D}[W] D ′ [ W ] = D [ W ] . Otherwise, D ′ [ W ] = D [ W ] + e \mathcal{D}'[W] = \mathcal{D}[W] + e D ′ [ W ] = D [ W ] + e . By Fact 3, G ∣ W ⪯ G ′ ∣ W \mathcal{G}|_W \preceq\mathcal{G}'|_W G ∣ W ⪯ G ′ ∣ W , and the ranks of G ∣ W \mathcal{G}|_W G ∣ W and G ′ ∣ W \mathcal{G}'|_W G ′ ∣ W differ by one. The poset over W W W is graded, so G ∣ W \mathcal{G}|_W G ∣ W and G ′ ∣ W \mathcal{G}'|_W G ′ ∣ W are neighbors.
Paths. Along a path, consecutive restrictions are therefore equal or neighbors. Removing repetitions gives a path from G s ∣ W \mathcal{G}_s|_W G s ∣ W to G t ∣ W \mathcal{G}_t|_W G t ∣ W whose steps are the operations on pairs inside W W W . By the definition of d W d_W d W , this path has at least d W ( G s ∣ W , G t ∣ W ) d_W(\mathcal{G}_s|_W,\mathcal{G}_t|_W) d W ( G s ∣ W , G t ∣ W ) steps.
Proposition 6 (Local mismatches). Let W ⊆ V W \subseteq V W ⊆ V . If
d W ( G s ∣ W , G t ∣ W ) > ∣ Skel ( G s ∣ W ) △ Skel ( G t ∣ W ) ∣ , d_W(\mathcal{G}_s|_W,\mathcal{G}_t|_W) > |\operatorname{Skel}(\mathcal{G}_s|_W) \mathbin{\triangle} \operatorname{Skel}(\mathcal{G}_t|_W)|, d W ( G s ∣ W , G t ∣ W ) > ∣ Skel ( G s ∣ W ) △ Skel ( G t ∣ W ) ∣ ,
then the set M W M_W M W of detour operations on pairs inside W W W is a mismatch for ( G s , G t ) (\mathcal{G}_s,\mathcal{G}_t) ( G s , G t ) .
Proof. By Lemma 8, the steps of a path from G s \mathcal{G}_s G s to G t \mathcal{G}_t G t that act on pairs inside W W W form a path from G s ∣ W \mathcal{G}_s|_W G s ∣ W to G t ∣ W \mathcal{G}_t|_W G t ∣ W , with at least d W ( G s ∣ W , G t ∣ W ) d_W(\mathcal{G}_s|_W,\mathcal{G}_t|_W) d W ( G s ∣ W , G t ∣ W ) steps. By assumption, this number exceeds the skeleton difference on W W W . By (6) over W W W , a path with more steps than the skeleton difference on W W W has a detour step. That step moves a pair inside W W W away from its state in G t ∣ W \mathcal{G}_t|_W G t ∣ W , which is its state in G t \mathcal{G}_t G t . The corresponding step of the original path therefore performs an operation of M W M_W M W .
Each pattern of § 6.2 gives a mismatch. A pattern occurs on a vertex set W W W when the restrictions G s ∣ W \mathcal{G}_s|_W G s ∣ W and G t ∣ W \mathcal{G}_t|_W G t ∣ W are the two graphs of the pattern, up to a relabeling of the vertices. The pattern of Figure 7 (a) occurs on W W W exactly when W W W carries a forbidden triple, with either graph containing the v-structure. By Lemma 4, the set M 1 M_1 M 1 is then a mismatch. For the four-vertex patterns, an enumeration of the 185 CPDAGs on four vertices gives distances 3, 4, 4 and 4 for the pairs in Figure 7 (b) and Figure 8 (a)–(Figure 8 c). The corresponding skeleton differences are 1, 2, 2 and 0. Each distance exceeds its skeleton difference, so Proposition 6 applies. Since d W d_W d W is symmetric, Proposition 6 applies whichever of the two graphs plays the role of G t \mathcal{G}_t G t . The resulting mismatch M W M_W M W consists of the detour operations on pairs inside W W W , relative to G t \mathcal{G}_t G t . The sets M 2 , … , M 5 M_2,\ldots,M_5 M 2 , … , M 5 of § 6.2 equal M W M_W M W when G t ∣ W \mathcal{G}_t|_W G t ∣ W is the lower graph of the figure. When G t ∣ W \mathcal{G}_t|_W G t ∣ W is the upper graph, ER and EA are exchanged on the pairs in which the two skeletons differ.
Disjoint stray edges
Lemma 9. Let D \mathcal{D} D be a DAG containing a set of disjoint stray edges E s t r a y \mathcal{E}_{\mathrm{stray}} E stray . Let D ′ \mathcal{D}' D ′ be the subgraph obtained by removing E s t r a y \mathcal{E}_{\mathrm{stray}} E stray from D \mathcal{D} D . Let Op \operatorname{Op} Op be any valid operation on an edge h h h whose endpoints lie entirely within the conflict set V Δ V_{\Delta} V Δ . If Op \operatorname{Op} Op is valid in D \mathcal{D} D , then Op \operatorname{Op} Op is also valid in D ′ \mathcal{D}' D ′ .
Proof. We examine the three types of operations.
Deletion. Consider the deletion of an edge h h h . If h ∈ E ( D ) h \in E(\mathcal{D}) h ∈ E ( D ) and its endpoints are in V Δ V_{\Delta} V Δ , then h ∉ E s t r a y h \notin\mathcal{E}_{\mathrm{stray}} h ∈ / E stray . Thus h ∈ E ( D ′ ) h \in E(\mathcal{D}') h ∈ E ( D ′ ) , and deleting an edge from a DAG always yields a DAG.
Addition. Validity here depends on acyclicity. If adding h h h to D \mathcal{D} D does not create a cycle, then adding h h h to a subgraph D ′ ⊂ D \mathcal{D}' \subset\mathcal{D} D ′ ⊂ D cannot create a cycle.
Covered edge reversal. Consider the reversal of a covered edge h = a → b h = a \to b h = a → b in D \mathcal{D} D . The covering condition requires
Pa D ( b ) = Pa D ( a ) ∪ { a } . \operatorname{Pa}_{\mathcal{D}}(b) = \operatorname{Pa}_{\mathcal{D}}(a) \cup\{a\}. Pa D ( b ) = Pa D ( a ) ∪ { a } .
By the definition of disjoint stray edges, any edge e = { u , v } ∈ E s t r a y e = \{u,v\} \in\mathcal{E}_{\mathrm{stray}} e = { u , v } ∈ E stray satisfies { u , v } ∩ V Δ = ∅ \{u,v\} \cap V_{\Delta} = \varnothing { u , v } ∩ V Δ = ∅ . Since a , b ∈ V Δ a,b \in V_{\Delta} a , b ∈ V Δ , no stray edge is incident to a a a or b b b . So removing E s t r a y \mathcal{E}_{\mathrm{stray}} E stray does not change the parent sets of a a a or b b b :
Pa D ′ ( a ) = Pa D ( a ) , Pa D ′ ( b ) = Pa D ( b ) . \operatorname{Pa}_{\mathcal{D}'}(a) = \operatorname{Pa}_{\mathcal{D}}(a), \qquad\operatorname{Pa}_{\mathcal{D}'}(b) = \operatorname{Pa}_{\mathcal{D}}(b). Pa D ′ ( a ) = Pa D ( a ) , Pa D ′ ( b ) = Pa D ( b ) .
Therefore, the covering condition holds in D ′ \mathcal{D}' D ′ . The operation remains a covered edge reversal and is therefore valid in the subgraph.
Proof of Proposition 5. We proceed by contradiction. Assume there exists a shortest path P = ( G 0 , … , G k ) P = (\mathcal{G}_0,\ldots,\mathcal{G}_k) P = ( G 0 , … , G k ) from G s = G 0 \mathcal{G}_s = \mathcal{G}_0 G s = G 0 to G t = G k \mathcal{G}_t = \mathcal{G}_k G t = G k in the poset L \mathcal{L} L such that some intermediate graph contains a disjoint stray edge in its skeleton. By Lemma 2, there exists a valid sequence of DAGs D 0 , … , D m \mathcal{D}_0,\ldots,\mathcal{D}_m D 0 , … , D m representing this path. Let E s t r a y \mathcal{E}_{\mathrm{stray}} E stray be the set of all disjoint stray edges appearing in any graph in this sequence. We construct a new sequence D ~ 0 , … , D ~ m \widetilde{\mathcal{D}}_0,\ldots,\widetilde{\mathcal{D}}_m D 0 , … , D m , where
D ~ j = ( V , E ( D j ) ∖ E s t r a y ) . \widetilde{\mathcal{D}}_j = (V, E(\mathcal{D}_j) \setminus\mathcal{E}_{\mathrm{stray}}). D j = ( V , E ( D j ) ∖ E stray ) .
By Lemma 9, all operations in the original sequence that acted on the conflict set V Δ V_{\Delta} V Δ remain valid in the new sequence. Operations that added or removed edges in E s t r a y \mathcal{E}_{\mathrm{stray}} E stray are omitted.
Since E s t r a y ∩ Skel ( G s ) = ∅ \mathcal{E}_{\mathrm{stray}} \cap\operatorname{Skel}(\mathcal{G}_s) = \varnothing E stray ∩ Skel ( G s ) = ∅ and E s t r a y ∩ Skel ( G t ) = ∅ \mathcal{E}_{\mathrm{stray}} \cap\operatorname{Skel}(\mathcal{G}_t) = \varnothing E stray ∩ Skel ( G t ) = ∅ , the new sequence still starts at a representative of G s \mathcal{G}_s G s and ends at a representative of G t \mathcal{G}_t G t . The original path P P P must have included rank-changing operations to add and subsequently delete every disjoint stray edge in E s t r a y \mathcal{E}_{\mathrm{stray}} E stray , since these edges are absent in both G s \mathcal{G}_s G s and G t \mathcal{G}_t G t . In the pruned sequence D ~ \widetilde{\mathcal{D}} D , these operations are removed. Thus, the CPDAG path corresponding to D ~ \widetilde{\mathcal{D}} D is strictly shorter than P P P , which contradicts the assumption that P P P is a shortest path. □
Appendix E. Additional experiments
Confidence regions for sparse graphs
We sample 600 instances (20 population SEMs each with 30 independent datasets) for weak, moderate, and strong signaled sparse graphs (See Table 1 ). We construct confidence balls and intervals with our proposed threshold (See § 4.2.4 ) and that of Chang et al. [4 ] and report confidence ball mean radius and coverage in Figure 17 and confidence interval mean width and coverage in Figure 18 over these instances. Note that the confidence ball coverage and radius for the weak signal setting (minimum partial correlations in 0.005-0.05) is reported in Figure 1 . Table 3 includes average common edge counts between the upper and lower graphs from the interval for each minimum partial correlation range over sample size.
Figure 17. Confidence ball results for the sparse p = 10 p = 10 p = 10 regimes with minimum nonzero partial correlations in [0.05, 0.10] (left) and [0.10, 0.20] (right). Top: empirical coverage. Bottom: mean radius.
Figure 18. Confidence interval results for the sparse p = 10 p = 10 p = 10 regimes with minimum nonzero partial correlations in [ 0.005 , 0.05 ] [0.005, 0.05] [ 0.005 , 0.05 ] (left), [ 0.05 , 0.10 ] [0.05, 0.10] [ 0.05 , 0.10 ] (middle), and [ 0.10 , 0.20 ] [0.10, 0.20] [ 0.10 , 0.20 ] (right). Top: empirical coverage. Bottom: mean interval width.
Table 3. Average number of edges shared by the lower and upper graphs in the sparse p = 10 p = 10 p = 10 setting across sample sizes and partial-correlation ranges.
Additional experiments for model-oriented distance under structural proximity
We report timeout rates of our method for the model-oriented distance and that of Taeb et al. [53 ] under structural proximity in § 8.2 . Here, we include additional timeout rates for the disconnected components regime for q i n = 0.5 q_{\mathrm{in}} = 0.5 q in = 0.5 in Figure 19 and the polytree regime for q t r e e = 0.5 q_{\mathrm{tree}} = 0.5 q tree = 0.5 and q t r e e = 1 q_{\mathrm{tree}} = 1 q tree = 1 in Figure 20 and Figure 21 , respectively.
Figure 19. Timeout rates for model-oriented distance searches between CPDAG pairs in the disconnected-component regime, with q i n = 0.5 q_{\mathrm{in}} = 0.5 q in = 0.5 and m ∈ { 0 , 1 , 3 , 7 } m \in\{0,1,3,7\} m ∈ { 0 , 1 , 3 , 7 } . Columns correspond to p = 10 , 15 , 20 , 30 , p = 10, 15, 20, 30, p = 10 , 15 , 20 , 30 , and 100 100 100 ; rows correspond to m m m . Solid and dashed curves use block sizes three and five, respectively. Each point is the proportion of the 100 pairs not solved within the indicated time budget; shaded regions show one standard deviation around that proportion. The curves compare the model-oriented-distance A ∗ A^{*} A ∗ procedure of Taeb et al. [53 ] with our procedure without the disconnected-component upper bound and with our procedure using the disconnected-component upper bound.
Figure 20. Timeout rates for model-oriented distance searches between CPDAG pairs near the polytree class, with q t r e e = 0.5 q_{\mathrm{tree}} = 0.5 q tree = 0.5 and c ∈ { 0 , 1 , 3 , 7 } c \in\{0,1,3,7\} c ∈ { 0 , 1 , 3 , 7 } . Columns correspond to p = 10 , 15 , 20 , 30 p = 10,15,20,30 p = 10 , 15 , 20 , 30 , and 100 100 100 ; rows correspond to c c c . Each point is the proportion of the 100 pairs not solved within the indicated time budget; shaded regions show one standard deviation around that proportion. The curves compare the model-oriented-distance A ∗ A^{*} A ∗ procedure of Taeb et al. [53 ] with our procedure without the polytree upper bound and with our procedure using the polytree upper bound.
Figure 21. Timeout rates for model-oriented distance searches between CPDAG pairs near the polytree class, with q t r e e = 1 q_{\mathrm{tree}} = 1 q tree = 1 and c ∈ { 0 , 1 , 3 , 7 } c \in\{0, 1, 3, 7\} c ∈ { 0 , 1 , 3 , 7 } . Columns correspond to p = 10 , 15 , 20 , 30 , p = 10, 15, 20, 30, p = 10 , 15 , 20 , 30 , and 100 100 100 ; rows correspond to c c c . Each point is the proportion of the 100 pairs not solved within the indicated time budget; shaded regions show one standard deviation around that proportion. The curves compare the model-oriented-distance A* procedure of Taeb et al. [53 ] with our procedure without the polytree upper bound and with our procedure using the polytree upper bound.