Back to Blog

Orienting graphs in aGrUM/pyAgrum

The new graph classes of aGrUM represent sets of DAGs: a CPDAG represents a Markov equivalence class, an MPDAG a class restricted by background knowledge, a PAG a class of ancestral graphs. Going from one of these graphs to another, or back to a single DAG, means orienting edges, and orienting them correctly: without creating a directed cycle, and without creating or destroying a v-structure (X->Z<-Y with X and Y not adjacent), since that would change the independence model.

This note presents the orientation algorithms that come with the next version of aGrUM/pyAgrum (after 3.3.2):

  1. from a PDAG to one of its DAGs (a consistent extension),
  2. from a DAG to its CPDAG,
  3. from a PDAG to its Meek closure (the MPDAG),
  4. from a learned graph to a DAG with minimal conditional probability tables,
  5. from a PAG to a representative MAG, as used by FCI.

1. Consistent extension: one DAG of a PDAG

A consistent extension of a PDAG is a DAG with the same skeleton and the same v-structures that contains all its arcs: its undirected edges are oriented without creating a directed cycle nor a new v-structure. A PDAG is extendable when it has one. This is the basic question behind everything else: “is there a DAG behind this partially oriented graph, and which one?”

The classical algorithm is due to Dor and Tarsi (1992). It looks for a potential sink: a node s

  • without child,
  • whose undirected neighbours form a clique,
  • and are all adjacent to all its parents.
a potential sink s
s is a potential sink

Such a node can safely be the last one of the DAG: all its edges are oriented towards it (here x->s, y->s), which creates no cycle (it has no child) and no new v-structure (all its future parents are already adjacent). Then s is removed and the search starts again. If no potential sink remains while edges are left, the PDAG is not extendable.

an extendable PDAG
An extendable PDAG
a consistent extension
One of its consistent extensions
a non-extendable 4-cycle
A non-extendable PDAG

The undirected 4-cycle A-B-C-D-A is the simplest non-extendable PDAG: whatever the orientation, either a directed cycle or a v-structure (between two non-adjacent nodes) appears, so it represents no DAG at all.

Implemented naively (testing the nodes again after each removal), this algorithm is cubic or worse. aGrUM implements the algorithm of Wienöbst, Bannach and Liśkiewicz (2021): two counters per node (the number of adjacent pairs among its undirected neighbours, and between its undirected neighbours and its parents) tell in constant time whether a node is a potential sink, and they are updated each time an edge is inserted or removed. The total time is O(dm) expected, where m is the number of edges and arcs and d the degeneracy of the skeleton (a measure of its sparsity: d is small for trees, planar graphs, and most learned graphs). The authors use a dedicated removal operation to get this bound; we showed that it already holds for the generic update, by an argument of Chiba and Nishizeki (1985): each update scans the smallest of the two adjacency lists, and the sum of these minima over all the edges is at most 2·d·m.

pdag = gum.fastGraph("A->B;B-C;C-D;B-D")
mpdag = gum.MPDAG.meekClosure(pdag) # raises InvalidArgument if pdag is not extendable
dag = mpdag.consistentExtension()

In C++, the function is gum::graph::consistentExtension(pdag), which returns an empty std::optional when the PDAG is not extendable.

2. From a DAG to its CPDAG

The CPDAG of a DAG keeps its compelled arcs (the ones with the same orientation in all the equivalent DAGs) and turns the reversible ones into undirected edges. Chickering (1995) gave a linear algorithm: the arcs are sorted (heads by increasing topological rank, then tails by decreasing rank), and each arc is labelled “compelled” or “reversible” by looking only at the arcs into its tail and into its head.

a DAG
A DAG
its CPDAG
Its CPDAG (compelled arcs in red)
dag = gum.fastGraph("A->C;B->C;C->D;D->E;A->F;F->E")
cpdag = gum.CPDAG.fromDAG(dag) # compelled arcs in red, A-F reversible

Combined with the consistent extension, this gives a cheap check that a PDAG is a CPDAG (CPDAG.fromPDAG): extend it, compute the CPDAG of the extension, and compare. EssentialGraph (the essential graph of a Bayesian network, with the names of its variables) is now a CPDAG: built from a model by Find-Compelled in linear time, and checked this way when it is built from a PDAG.

3. Meek rules and Meek closure

When some arcs of a CPDAG are imposed (background knowledge, interventions, learned arcs), other edges become forced. Meek (1995) gave four rules; each one orients the red edge as shown (the conditions are under each rule), because the other orientation would create a new v-structure or a directed cycle:

R1
R1 (a, c not adjacent)
R2
R2 (avoid a cycle)
R3
R3 (a, c not adjacent)
R4
R4 (a, p adjacent; d, v not adjacent)
  • R1: a->b-c with a and c not adjacent: c->b would create the v-structure a->b<-c, so b->c.
  • R2: a->b->c and a-c: c->a would close a directed cycle, so a->c.
  • R3: b-a, b-c, a->d<-c, b-d, with a and c not adjacent: d->b would force a->b<-c, a new v-structure, so b->d.
  • R4: a-d, d->p->v, a-v, a adjacent to p and d not adjacent to v. As in Figure 1 of Meek (1995), the link between a and p is dashed: it may be a-p, a->p or p->a. Then v->a would force d->a (since a->d would close the cycle d->p->v->a->d), hence the new v-structure d->a<-v; so a->v.

Applying these rules until nothing changes gives the Meek closure of the PDAG, its MPDAG. Meek (1995) proved that the rules are sound (Theorem 2) and complete: applied to the pattern of a DAG (its skeleton and v-structures), R1, R2 and R3 already give the maximally oriented graph, the CPDAG (Theorem 3); with background knowledge, R1 to R4 give the maximally oriented graph with respect to this knowledge (Theorem 4). Maximally oriented means that every edge left unoriented is oriented one way in some consistent extension and the other way in another one.

Applied naively (scan all the rules on all the edges, again and again), the closure costs up to O(n⁴m) (Luttermann, Wienöbst and Liśkiewicz 2023). aGrUM implements the algorithm of Wienöbst, Bannach and Liśkiewicz (2021) instead:

  1. compute a consistent extension D of the PDAG (if there is none, the closure is not defined);
  2. compute the CPDAG of D: its arcs are in every DAG of the class, hence in the closure, so only its undirected edges remain to examine;
  3. re-impose the arcs of the PDAG;
  4. visit the nodes once, in a topological order of D, and apply R1, R4 and R2 to the edges into the current node (R3 never applies inside a chain component of a CPDAG).

This takes O(dm) expected. In our measures (3000 nodes, degree 6), the closure of a chordal graph with 2% of arcs went from 1883 ms (former fixpoint) to 47 ms.

a PDAG
A PDAG
its Meek closure
Its Meek closure

Here A->B-C and A->B-D with A adjacent to neither C nor D: R1 gives B->C and B->D. The edge C-D stays undirected: both C->D and D->C are possible.

mpdag = gum.MPDAG.meekClosure(gum.fastGraph("A->B;B-C;C-D;B-D"))
mpdag.arcs(), mpdag.graph().edges() # A->B, B->C, B->D ; C-D

gum.MeekRules (used by the constraint-based learners) now uses this closure whenever its input is extendable, and keeps its former propagation only for the non-extendable graphs that noisy data can produce.

4. From a learned graph to a DAG with small CPTs

A constraint-based learner (PC, MIIC) learns an equivalence class; but a Bayesian network needs a DAG. Any consistent extension would do for the independences, but not for the size of the model: the total size of the conditional probability tables,

∑v∣v∣⋅∏u∈pa(v)∣u∣,\sum_{v} |v| \cdot \prod_{u \in \mathrm{pa}(v)} |u|,

where |v| is the domain size of v, depends on the chosen DAG. Take the path A-B-C with domain sizes 4, 5 and 5. All its orientations without v-structure are equivalent, but:

rootDAGtotal size of the CPTs
AA->B->C4 + 4·5 + 5·5 = 49
BA<-B->C5 + 5·4 + 5·5 = 50
CA<-B<-C5 + 5·5 + 5·4 = 50

(Equivalent DAGs are linked by reversals of covered arcs (Chickering 1995), which do not change the number of free parameters: minimizing the total size of the CPTs amounts to minimizing the number of parent configurations.)

A natural greedy strategy runs the Dor-Tarsi algorithm, removing at each step the potential sink with the smallest CPT. On this path, it first removes A (CPT 4·5 = 20 < 25), then hesitates between B and C (both 5·5 = 25) and ends with 50:

the path
The path (domain sizes)
greedy: 50
Greedy: 50
optimal: 49
Optimal: 49

On random chordal graphs of 4 to 8 nodes, the greedy choice misses the minimum in about half the cases (3.7% larger on average in those cases, up to 22%). The new gum::graph::orientAsDAG(pdag, domainSizes) computes the exact minimum, by turning a counting algorithm into an optimization one:

  • in a CPDAG, all the nodes of an undirected component have the same parents outside it, so the components can be oriented independently;
  • each component is a connected chordal graph, and its DAGs are its orientations without v-structure. The Clique-Picking algorithm of Wienöbst, Bannach and Liśkiewicz (2021, 2023) counts them: every such orientation starts with a maximal clique K; once K is placed first, the remaining undirected components are again chordal, have common parents, and are independent;
  • for a count, the orientations reached from several cliques must be corrected for; for a minimum, these overlaps do not matter. Hence the recursion

cost(H)=min⁡K[cost(K)+∑C(∏p∈paH(C)∣p∣)⋅cost(C)],\mathrm{cost}(H) = \min_{K} \Big[ \mathrm{cost}(K) + \sum_{C} \Big(\prod_{p \in \mathrm{pa}_H(C)} |p|\Big)\cdot \mathrm{cost}(C) \Big],

memoized on the components (at most 2|Π(H)|−1 of them, |Π(H)| being the number of maximal cliques), where the nodes of K are ordered by increasing domain size, which minimizes the sum of the prefix products.

This exact algorithm runs in O(|Π(H)|²·d·m) for a component H: a few tens of milliseconds for 100 nodes, but several seconds for 1000. Above a size given by the configuration (gum.config["graph", "orientAsDAGExactMaxSize"], 100 nodes by default), a component is oriented by the greedy heuristic. The greedy heuristic is also used when the PDAG is not extendable (some edges are then oriented as if their head were a sink, which creates v-structures but always gives a DAG), or when background knowledge breaks the “common parents” property.

This is what the constraint-based learners (MIIC, PC, FCI) now do in learnDAG(), with the domain sizes of the variables:

bn = gum.fastBN("A[10]->B[2]->C[10]")
generator = gum.BNDatabaseGenerator(bn)
generator.drawSamples(20000)
learner = gum.BNLearner(generator.to_pandas())
learner.useMIIC()
learner.learnPDAG() # A-B-C : the direction cannot be learned
learner.learnDAG() # B->A, B->C : B, with only 2 values, becomes the root

learner.learnEssentialGraph() gives the CPDAG of this learned DAG, whatever the algorithm; the learned PDAG itself, which may not be a CPDAG with noisy data, remains given by learnPDAG().

5. From a PAG to a MAG, and FCI

The FCI algorithm (Spirtes, Glymour and Scheines 2000; Zhang 2008) learns a PAG: a class of MAGs (ancestral graphs, for models with latent variables), with circles for the undetermined marks. To get one graph of the class, Zhang (2008, Theorem 2) gives a simple construction of a representative MAG:

  • the edges o-> and -o become ->;
  • the edges o-o form chordal components, which are oriented into a DAG without unshielded collider (with the consistent extension of section 1).
a PAG
A PAG
a representative MAG
Its representative MAG
pag = gum.fastPAG("A o-> B;C o-> B;B -> D;C o-o E")
mag = gum.MAG.fromPAG(pag) # A->B<-C, B->D, C->E

FCI.learnPDAG() and learnDAG() now go through this representative MAG, instead of pushing the PAG into the Meek rules as if it were a PDAG (which was not correct). When the learned PAG is not valid (its representative graph has a directed cycle, which can happen with noisy data), the configuration key learning.fciErrorOnInvalidPAG chooses between an error and the former approximation.

In short

fromtoalgorithmtime
PDAGone of its DAGsDor-Tarsi with the counters of Wienöbst et al. 2021O(dm) expected
DAGits CPDAGChickering 1995O(n + m) after a topological sort
PDAGits Meek closure (MPDAG)Wienöbst et al. 2021 (extension, CPDAG, one pass of R1, R4, R2)O(dm) expected
CPDAG + domain sizesDAG with minimal total CPT sizeClique-Picking turned into a minimizationO(|Π|²·d·m) per component
PAGa representative MAGZhang 2008, Theorem 2dominated by the extension

The graph algorithms used along the way (LexBFS, maximum cardinality search, chordality, degeneracy ordering…) will be the subject of another note.

References

  • N. Chiba, T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing 14(1):210-223, 1985. doi:10.1137/0214017
  • D. M. Chickering. A transformational characterization of equivalent Bayesian network structures. UAI 1995, pp. 87-98. arXiv:1302.4938
  • D. Dor, M. Tarsi. A simple algorithm to construct a consistent extension of a partially oriented graph. Technical Report R-185, UCLA Cognitive Systems Laboratory, 1992. PDF
  • M. Luttermann, M. Wienöbst, M. Liśkiewicz. Practical algorithms for orientations of partially directed graphical models. CLeaR 2023, PMLR 213:259-280. PMLR
  • C. Meek. Causal inference and causal explanation with background knowledge. UAI 1995, pp. 403-410. arXiv:1302.4972
  • P. Spirtes, C. Glymour, R. Scheines. Causation, Prediction, and Search, 2nd edition. MIT Press, 2000. IDEAS record
  • M. Wienöbst, M. Bannach, M. Liśkiewicz. Extendability of causal graphical models: algorithms and computational complexity. UAI 2021, PMLR 161:1248-1257. PMLR
  • M. Wienöbst, M. Bannach, M. Liśkiewicz. Polynomial-time algorithms for counting and sampling Markov equivalent DAGs. AAAI 2021, 35(13):12198-12206; extended version with applications in JMLR 24(213):1-45, 2023. doi:10.1609/aaai.v35i13.17448, JMLR
  • J. Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence 172(16-17):1873-1896, 2008. doi:10.1016/j.artint.2008.08.001