A new hierarchy of graphs in aGrUM/pyAgrum
A Bayesian network is a DAG. But as soon as one learns a Bayesian network from data, or asks causal questions, other graphs appear: graphs with undirected edges (the data could not tell the direction of an arc), with bidirected edges (a hidden common cause), or with circles (we do not even know which mark is there). Each of these graphs represents a set of DAGs, and each one comes with its own rules.
Until now, aGrUM had a single PDAG class (and a PAG class with no real invariant) to cover all these cases. The
next version of aGrUM/pyAgrum (after 3.3.2) comes with a set of graph classes that follows the definitions of
Andersson, Madigan and Perlman (1997) for the CPDAG, of Wienöbst, Bannach and Liśkiewicz (2021) for the PDAG, the
chain graph and the MPDAG, and of Richardson and Spirtes (2002) and Zhang (2008) for the ancestral graphs. This note
introduces the notions and shows how they are organized. A companion note presents the
orientation algorithms that go with them.
In this figure, the gray classes are mutable graphs (one can add or remove nodes, arcs and edges), the blue ones are certified graphs (immutable values, built and checked by an algorithm), which share a read-only base. Let us see why.
Four kinds of links
A graph is made of nodes and links between them. The ancestral graphs of Richardson and Spirtes (2002) and the
partial ancestral graphs of Zhang (2008) use four kinds of links, which can all be described
by the marks at their two ends: a tail (nothing), an arrowhead (>) or a circle (o).
| link | marks | reading |
|---|---|---|
A -> B (arc) | tail, arrowhead | A is a cause (an ancestor) of B |
C <-> D (bidirected edge) | arrowhead, arrowhead | C and D have a hidden common cause |
E - F (undirected edge) | tail, tail | the direction is unknown (or, with selection bias, both are ancestors of a selected node) |
G o-> H, I o-o J | circle | the mark is unknown: it may be a tail or an arrowhead |
The first and third kinds give the classical mixed graphs; all four of them are handled by the new
MarkedGraph class, where every edge carries a mark at each end.
import pyagrum as gum
g = gum.fastMarkedGraph("A->B;C<->D;E-F;G o-> H;I o-o J")g.markAt(g.idFromName("G"), g.idFromName("H")) # EdgeMark.Arrowhead: the mark at Hg.markAt(g.idFromName("H"), g.idFromName("G")) # EdgeMark.Circle: the mark at GPDAG and chain graphs
A PDAG (partially directed acyclic graph) mixes arcs and undirected edges, with at most one link between two
nodes, and no directed cycle (Wienöbst, Bannach and Liśkiewicz 2021, Section 2; see also Chickering 2002). That
is now exactly what gum.PDAG checks.
A PDAG may contain a cycle that uses both arcs and edges, as long as the arcs do not all go the same way around it:
Here A->B-C->A is a partially directed cycle: no directed cycle, so it is a valid PDAG. But it is not a chain
graph: a chain graph forbids partially directed cycles. The new ChainGraph class (a PDAG with this additional
invariant) is the structure of the LWF chain graph models (Lauritzen and Wermuth 1989; Frydenberg 1990) and of the
AMP ones (Andersson, Madigan and Perlman 2001). Its undirected connected components, the chain
components, are drawn in boxes:
pdag = gum.fastGraph("A->B;B-C;C->A") # a PDAGgum.ChainGraph(pdag) # raises InvalidPartiallyDirectedCycleBoth invariants are local: they can be checked each time an arc is added, so PDAG and ChainGraph remain
mutable graphs. (The former PDAG class of aGrUM was in fact a chain graph, and its cycle check had a bug; the
LWF-specific methods of PDAG such as moralGraph or cSeparation now belong to ChainGraph.)
Markov equivalence and CPDAG
Data alone cannot distinguish every DAG. Two DAGs are Markov equivalent when they encode the same conditional
independences; Verma and Pearl (1990) showed that this happens exactly when they have the same skeleton and the
same v-structures (X->Z<-Y with X and Y not adjacent). The first three DAGs below are equivalent, the fourth is
not (it has a v-structure):
A whole equivalence class is represented by a single graph, its CPDAG (completed PDAG, also called essential
graph): an arc is kept when it has the same orientation in every DAG of the class (it is compelled), and becomes
an undirected edge otherwise (it is reversible). Andersson, Madigan and Perlman (1997) characterized these graphs:
a CPDAG is a chain graph whose chain components are chordal, without induced a->b-c, and whose arcs are “strongly
protected”.
In the CPDAG of this DAG, the compelled arcs are drawn in red, and the only reversible arc
A->F became the edge A-F, in its chain component. Indeed, the DAG with F->A has the same skeleton and the same
v-structures (A->C<-B and D->E<-F).
dag = gum.fastGraph("A->C;B->C;C->D;D->E;A->F;F->E")cpdag = gum.CPDAG.fromDAG(dag)cpdag.arcs(), cpdag.graph().edges() # the compelled arcs, the edge A-Fcpdag.contains(dag) # TrueA, B, C = (dag.idFromName(n) for n in "ABC")cpdag.dSeparation(A, B) # True: d-separated in every DAG of the classcpdag.dSeparation(A, B, C) # False: C is a colliderContrary to the previous ones, this invariant is global: adding a single arc to a CPDAG generally gives a graph
that is no longer a CPDAG, and checking it requires a whole algorithm. That is why CPDAG is an immutable value:
it is built by CPDAG.fromDAG (Chickering 1995), or by CPDAG.fromPDAG which checks that the PDAG is really a
CPDAG. It gives read-only access to its graph, and consistentExtension() gives one DAG of the class, kept from its
construction: dSeparation is computed on this DAG, since all the DAGs of the class have the same d-separations.
The class EssentialGraph is a CPDAG built from a Bayesian network, with the names of its variables
(gum.EssentialGraph(bn)), or learned from data (learner.learnEssentialGraph(), the CPDAG of the learned DAG).
Background knowledge: MPDAG
Suppose we know, from the time order or from an experiment, that A causes B, while the CPDAG leaves this edge
undirected. Imposing A->B has consequences: by the Meek rules (presented in the companion note), other edges
must then be oriented to avoid new v-structures and cycles. The result is an MPDAG (maximally oriented PDAG,
Meek 1995; Perković et al. 2017):
In this CPDAG, the chain component A-B-C, B-D is undirected. In the MPDAG obtained with A->B, since
A is not adjacent to C nor D, B-C and B-D must be oriented away from B (rule R1), and here the whole
graph becomes a DAG.
dag = gum.fastGraph("A->B;B->C;B->D;C->E;D->E")A, B = dag.idFromName("A"), dag.idFromName("B")mpdag = gum.MPDAG.fromCPDAG(gum.CPDAG.fromDAG(dag), [(A, B)])An MPDAG is not always a chain graph (it may contain a partially directed cycle), which is why MPDAG holds a PDAG.
Like CPDAG, it is an immutable value: built by MPDAG.meekClosure(pdag), MPDAG.fromCPDAG(cpdag, arcs) or a
checked MPDAG.fromPDAG(pdag). It also keeps one of the DAGs it represents (consistentExtension()), on which its
dSeparation is computed.
Latent variables: MAG and PAG
When some variables are not observed (latent), or when the data were collected under some selection, the DAG
over the observed variables is no longer an adequate model. Ancestral graphs (Richardson and Spirtes 2002) keep
exactly the independences among the observed variables, using the marks: a bidirected edge B<->C means that B and
C are dependent through a hidden common cause, and none of them is an ancestor of the other.
In the MAG (maximal ancestral graph) of this DAG over A, B, C, D, the latent L disappears,
and B<->C keeps track of their common cause. The separation in a MAG is the m-separation: A and C are
m-separated, but they become dependent when one conditions on B (a collider).
dag = gum.fastGraph("A->B;L->B;L->C;C->D")mag = gum.MAG.fromDAG(dag, {dag.idFromName("L")}) # the latent nodesA, B, C = (mag.idFromName(n) for n in "ABC")mag.mSeparation(A, C) # Truemag.mSeparation(A, C, {B}) # FalseA MAG must be ancestral (no directed or almost-directed cycle) and maximal (two non-adjacent nodes can be
separated): another global invariant, so MAG is also an immutable value (MAG.fromDAG, MAG.fromMarkedGraph
which checks, MAG.fromPAG). As in the other graphs, mag.neighbours(x) gives the nodes linked to x by an
undirected edge x-y, while mag.adjacents(x) gives all the nodes linked to x, whatever the marks
(parents, children and spouses give the arcs and the bidirected edges).
Finally, Markov equivalent MAGs form a class represented by a PAG (partial ancestral graph), the output of the FCI algorithm (Spirtes, Glymour and Scheines 2000; Zhang 2008): a mark is a tail or an arrowhead when it is the same in every MAG of the class, a circle otherwise.
pag = gum.fastPAG("A o-> B;C o-> B;B -> D;C o-o E")PAG is now built on MarkedGraph: the marks can be read and modified one end at a time (markAt,
setMarkAt), and they are kept when a PAG is copied or pickled.
Saving and drawing
All these graphs (except CliqueGraph) can be saved in the native GUM format of aGrUM, in JSON (.jgum) or in
binary (.bgum), and are pickled through it: names, isolated nodes, marks and the class itself are kept, an
immutable CPDAG being reloaded as a CPDAG.
cpdag.saveGUM("class.jgum")same = gum.loadGraph("class.jgum") # a gum.CPDAGThey also share the same look in DOT (in a notebook, gnb.show(cpdag)): compelled arcs in red, and the chain
components of a ChainGraph or a CPDAG in boxes (a PDAG or an MPDAG is drawn without boxes: it may contain a
partially directed cycle). The colors come from the new dot section of the configuration
(gum.config["dot", "compelledArcColor"], "chainComponentBgColor", "bidirectedEdgeColor",
"circleMarkEdgeColor"…).
In short
The three immutable classes CPDAG, MPDAG and MAG share the same read-only interface: the accessors of their
graph (nodes, edges, existsEdge, nameFromId, idFromName…), connectedComponents(), skeleton(), and a
copy of their graph with graph().
| class | links | invariant | nature | represents |
|---|---|---|---|---|
DAG | -> | no directed cycle | mutable | a Bayesian network |
PDAG | ->, - | no directed cycle | mutable | a partially oriented graph |
ChainGraph | ->, - | no partially directed cycle | mutable | a chain graph model |
CPDAG | ->, - | Andersson et al. 1997 | immutable | a Markov equivalence class of DAGs |
MPDAG | ->, - | closed under the Meek rules | immutable | a class with background knowledge |
MarkedGraph | any marks | one edge per pair | mutable | storage for ancestral graphs |
MAG | ->, <->, - | ancestral and maximal | immutable | a DAG with latent/selected variables |
PAG | with circles | (checked on demand) | mutable | a Markov equivalence class of MAGs |
References
- S. A. Andersson, D. Madigan, M. D. Perlman. A characterization of Markov equivalence classes for acyclic digraphs. The Annals of Statistics 25(2):505-541, 1997. doi:10.1214/aos/1031833662
- S. A. Andersson, D. Madigan, M. D. Perlman. Alternative Markov properties for chain graphs. Scandinavian Journal of Statistics 28(1):33-85, 2001. doi:10.1111/1467-9469.00224
- D. M. Chickering. A transformational characterization of equivalent Bayesian network structures. UAI 1995, pp. 87-98. arXiv:1302.4938
- D. M. Chickering. Optimal structure identification with greedy search. JMLR 3:507-554, 2002. JMLR
- M. Frydenberg. The chain graph Markov property. Scandinavian Journal of Statistics 17(4):333-353, 1990. zbMATH 0713.60013
- S. L. Lauritzen, N. Wermuth. Graphical models for associations between variables, some of which are qualitative and some quantitative. The Annals of Statistics 17(1):31-57, 1989. doi:10.1214/aos/1176347003
- C. Meek. Causal inference and causal explanation with background knowledge. UAI 1995, pp. 403-410. arXiv:1302.4972
- E. Perković, M. Kalisch, M. H. Maathuis. Interpreting and using CPDAGs with background knowledge. UAI 2017, PMLR R15:461-470. PMLR
- T. Richardson, P. Spirtes. Ancestral graph Markov models. The Annals of Statistics 30(4):962-1030, 2002. doi:10.1214/aos/1031689015
- P. Spirtes, C. Glymour, R. Scheines. Causation, Prediction, and Search, 2nd edition. MIT Press, 2000. IDEAS record
- T. Verma, J. Pearl. Equivalence and synthesis of causal models. UAI 1990, pp. 255-270. MLAnthology
- M. Wienöbst, M. Bannach, M. Liśkiewicz. Extendability of causal graphical models: algorithms and computational complexity. UAI 2021, PMLR 161:1248-1257. PMLR
- 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