In
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a moral graph is used to find the equivalent undirected form of a
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...
. It is a key step of the
junction tree algorithm, used in
belief propagation
A belief is an attitude that something is the case, or that some proposition is true. In epistemology, philosophers use the term "belief" to refer to attitudes about the world which can be either true or false. To believe something is to take i ...
on
graphical models.
The moralized counterpart of a directed acyclic graph is formed by adding edges between all pairs of non-adjacent nodes that have a common child, and then making all edges in the graph undirected. Equivalently, a moral graph of a directed acyclic graph is an undirected graph in which each node of the original is now connected to its
Markov blanket. The name stems from the fact that, in a moral graph, two nodes that have a common child are required to be ''married'' by sharing an edge.
Moralization may also be applied to
mixed graph
In graph theory, a mixed graph is a graph consisting of a set of vertices , a set of (undirected) edges , and a set of directed edges (or arcs) .
Definitions and notation
Consider adjacent vertices u,v \in V. A directed edge, called an arc, ...
s, called in this context "chain graphs". In a chain graph, a connected component of the undirected subgraph is called a chain. Moralization adds an undirected edge between any two vertices that both have outgoing edges to the same chain, and then forgets the orientation of the directed edges of the graph.
Weakly recursively simplicial
A graph is weakly recursively simplicial if it has a
simplicial vertex and the subgraph after removing a simplicial vertex and some edges (possibly none) between its neighbours is weakly recursively simplicial. A graph is moral if and only if it is weakly recursively simplicial.
A
chordal graph (a.k.a., recursive simplicial) is a special case of weakly recursively simplicial when no edge is removed during the elimination process. Therefore, a chordal graph is also moral. But a moral graph is not necessarily chordal.
[, p. 50.]
Recognising moral graphs
Unlike chordal graphs that can be recognised in polynomial time, proved that deciding whether or not a graph is moral is NP-complete.
See also
*
D-separation
A Bayesian network (also known as a Bayes network, Bayes net, belief network, or decision network) is a probabilistic graphical model that represents a set of variables and their conditional dependencies via a directed acyclic graph (DAG). Ba ...
*
Tree decomposition
References
*{{citation
, last1 = Verma , first1 = T. S.
, last2 = Pearl , first2 = J. , author2-link = Judea Pearl
, journal = Uncertainty in Artificial Intelligence
, pages = 391–399
, title = Deciding morality of graphs is NP-complete
, year = 1993, doi = 10.1016/B978-1-4832-1451-1.50052-4
, arxiv = 1303.1501, isbn = 9781483214511
, s2cid = 14690613
.
External links
M. Studeny: On mathematical description of probabilistic conditional independence structures
Bayesian networks
Graphical models
Graph operations