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 conne ...
, 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 ve ...
. It is a key step of the
junction tree algorithm
The junction tree algorithm (also known as 'Clique Tree') is a method used in machine learning to extract marginalization in general graphs. In essence, it entails performing belief propagation on a modified graph called a junction tree. The gra ...
, 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
''Graphical Models'' is an academic journal in computer graphics and geometry processing publisher by Elsevier. , its editor-in-chief is Jorg Peters of the University of Florida.
History
This journal has gone through multiple names. Founded in 1 ...
.
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
In statistics and machine learning, when one wants to infer a random variable with a set of variables, usually a subset is enough, and other variables are useless. Such a subset that contains all the useful information is called a 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). Bay ...
*
Tree decomposition
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.
Tree decompositions are also called junction trees ...
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