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):
- from a PDAG to one of its DAGs (a consistent extension),
- from a DAG to its CPDAG,
- from a PDAG to its Meek closure (the MPDAG),
- from a learned graph to a DAG with minimal conditional probability tables,
- 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.
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.
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 extendabledag = 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.
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 reversibleCombined 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:
a->b-cwithaandcnot adjacent:c->bwould create the v-structurea->b<-c, sob->c. - R2:
a->b->canda-c:c->awould close a directed cycle, soa->c. - R3:
b-a,b-c,a->d<-c,b-d, withaandcnot adjacent:d->bwould forcea->b<-c, a new v-structure, sob->d. - R4:
a-d,d->p->v,a-v,aadjacent topanddnot adjacent tov. As in Figure 1 of Meek (1995), the link betweenaandpis dashed: it may bea-p,a->porp->a. Thenv->awould forced->a(sincea->dwould close the cycled->p->v->a->d), hence the new v-structured->a<-v; soa->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:
- compute a consistent extension
Dof the PDAG (if there is none, the closure is not defined); - 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; - re-impose the arcs of the PDAG;
- 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.
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-Dgum.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,
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:
| root | DAG | total size of the CPTs |
|---|---|---|
| A | A->B->C | 4 + 4·5 + 5·5 = 49 |
| B | A<-B->C | 5 + 5·4 + 5·5 = 50 |
| C | A<-B<-C | 5 + 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:
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; onceKis 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
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 learnedlearner.learnDAG() # B->A, B->C : B, with only 2 values, becomes the rootlearner.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-obecome->; - the edges
o-oform chordal components, which are oriented into a DAG without unshielded collider (with the consistent extension of section 1).
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->EFCI.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
| from | to | algorithm | time |
|---|---|---|---|
| PDAG | one of its DAGs | Dor-Tarsi with the counters of Wienöbst et al. 2021 | O(dm) expected |
| DAG | its CPDAG | Chickering 1995 | O(n + m) after a topological sort |
| PDAG | its Meek closure (MPDAG) | Wienöbst et al. 2021 (extension, CPDAG, one pass of R1, R4, R2) | O(dm) expected |
| CPDAG + domain sizes | DAG with minimal total CPT size | Clique-Picking turned into a minimization | O(|Π|²·d·m) per component |
| PAG | a representative MAG | Zhang 2008, Theorem 2 | dominated 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