Back to Blog

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.

the hierarchy of the graph classes
The graph classes: mutable graphs (gray), certified immutable values (blue) and their read-only bases (light blue)

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.

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).

arc, bidirected edge, undirected edge, circle marks
An arc, a bidirected edge, an undirected edge, and two edges with circle marks
linkmarksreading
A -> B (arc)tail, arrowheadA is a cause (an ancestor) of B
C <-> D (bidirected edge)arrowhead, arrowheadC and D have a hidden common cause
E - F (undirected edge)tail, tailthe direction is unknown (or, with selection bias, both are ancestors of a selected node)
G o-> H, I o-o Jcirclethe 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 H
g.markAt(g.idFromName("H"), g.idFromName("G")) # EdgeMark.Circle: the mark at G

PDAG 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:

a partially directed cycle A to B-C to A
A partially directed cycle: a PDAG, not a chain graph

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:

a chain graph with a chain component C-D-E
A chain graph and its chain component {C, D, E}
pdag = gum.fastGraph("A->B;B-C;C->A") # a PDAG
gum.ChainGraph(pdag) # raises InvalidPartiallyDirectedCycle

Both 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 to B to C
(a) equivalent
A from B from C
(b) equivalent
A from B to C
(c) equivalent
A to B from C
(d) a v-structure: not equivalent

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”.

a DAG
A DAG
its CPDAG
Its CPDAG (compelled arcs in red)

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-F
cpdag.contains(dag) # True
A, B, C = (dag.idFromName(n) for n in "ABC")
cpdag.dSeparation(A, B) # True: d-separated in every DAG of the class
cpdag.dSeparation(A, B, C) # False: C is a collider

Contrary 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):

a CPDAG
A CPDAG
the MPDAG with A to B
Its MPDAG with A→B imposed

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.

a DAG with a latent node L
A DAG with a latent node L
its MAG over A, B, C, D
Its MAG over A, B, C, D

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 nodes
A, B, C = (mag.idFromName(n) for n in "ABC")
mag.mSeparation(A, C) # True
mag.mSeparation(A, C, {B}) # False

A 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.

a PAG
A PAG (circles: undetermined marks)
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.CPDAG

They 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().

classlinksinvariantnaturerepresents
DAG->no directed cyclemutablea Bayesian network
PDAG->, -no directed cyclemutablea partially oriented graph
ChainGraph->, -no partially directed cyclemutablea chain graph model
CPDAG->, -Andersson et al. 1997immutablea Markov equivalence class of DAGs
MPDAG->, -closed under the Meek rulesimmutablea class with background knowledge
MarkedGraphany marksone edge per pairmutablestorage for ancestral graphs
MAG->, <->, -ancestral and maximalimmutablea DAG with latent/selected variables
PAGwith circles(checked on demand)mutablea 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