Probabilistic graphical models generally fall into two camps: directed graphs (like Bayesian networks), which excel at representing asymmetric causal or generative processes, and undirected graphs (like Markov random fields), which naturally capture symmetric correlations.
At the heart of both frameworks lies the concept of conditional independence—determining whether two sets of variables are independent given a third. However, reading these independencies out of a graph requires completely different rules depending on edge directionality. In an undirected graph, independence is simple path separation: if every path between node $A$ and node $B$ is blocked by a set of observed nodes $C$, then $A$ is independent of $B$ given $C$. In a directed graph, we must instead use d-separation, a more complex criterion that accounts for the direction of information flow.
Graph moralization is the mathematical bridge that unifies these two paradigms. By systematically transforming a directed graph into an undirected one, moralization allows us to swap the complex rules of d-separation for the intuitive, computationally efficient tools of standard undirected graph separation.
The Core Intuition: The V-Structure Problem
Why can't we just drop the arrowheads from a directed graph to make it undirected? The obstacle is the v-structure (or collider), where two unlinked parent nodes point to a common child ($A \rightarrow C \leftarrow B$).
In a v-structure, $A$ and $B$ are marginally independent; they have no influence on each other. However, if we condition on the common child $C$ (or any of its descendants), $A$ and $B$ suddenly become dependent. This phenomenon is often called "explaining away." For example, if rain ($A$) and a broken sprinkler ($B$) can both cause a wet lawn ($C$), observing that the lawn is wet makes rain and a broken sprinkler mutually dependent; if we discover it didn't rain, the probability that the sprinkler is broken shoots up.
In standard undirected graph separation, conditioning on an intervening node blocks a path. But in a directed v-structure, conditioning on the intervening node opens the path.
To replicate this behavior in an undirected graph, we must explicitly add an edge between the parents $A$ and $B$ so that they remain connected even when we evaluate paths through the graph. This process is called moralization—metaphorically "marrying" the unmarried parents of a shared child. Once all co-parents are connected by undirected edges, all original directed arrows are dropped.
As Michael Jordan explains in his overview of Graphical Models, this transformation enables the application of unified undirected inference algorithms to models originally defined with causal or generative directions. Verma et al. demonstrate in Deciding Morality of Graphs is NP-complete that the resulting moral graph serves as the fundamental formal link between symmetric observational data and asymmetric causal models.
Algorithmic Utility: Simplifying d-Separation
Evaluating d-separation directly on a large directed acyclic graph (DAG) can be algorithmically cumbersome because the status of a path (active or blocked) changes dynamically based on which nodes are conditioned on. Moralization simplifies this by reducing d-separation to a static vertex-cut problem.
To determine if $A$ is d-separated from $B$ given $C$ in a DAG:
- Identify the ancestral subgraph containing only $A$, $B$, $C$, and their ancestors. (Ancestors must be preserved because v-structures only activate if the child or its descendants are conditioned on).
- Moralize this subgraph by connecting all co-parents.
- Drop the edge directions to form an undirected graph.
Now, if $C$ separates $A$ and $B$ in this new undirected graph via simple path blocking, then $A$ is guaranteed to be d-separated from $B$ given $C$ in the original DAG.
Directed DAG (v-structure) Moralized Undirected Graph
A B A ------- B
\ / \ /
\ / \ /
v v \ /
C C
This reduction unlocks powerful algorithmic optimizations. For instance, Acid et al. show in An Algorithm for Finding Minimum d-Separating Sets in Belief Networks that finding the smallest set of variables required to isolate two target variables can be solved efficiently by finding a minimum separating vertex cut on the undirected moral graph.
Similarly, van der Zander et al. extend this paradigm to mixed graphs (which contain both directed and bi-directed edges representing latent confounding) in Constructing Separators and Adjustment Sets in Ancestral Graphs and their subsequent Corrigendum. They demonstrate that ancestral graph moralization allows polynomial-time algorithms to compute valid covariate adjustment sets, which are vital for eliminating bias in causal inference. This operationalizes early foundational insights by Geiger et al. in d-Separation: From Theorems to Algorithms, which first mapped abstract d-separation criteria onto concrete path-finding routines.
Computational Inference: Junction Trees and Decomposable Graphs
Beyond reading independence properties, moralization is the indispensable first step for exact probabilistic inference in Bayesian networks.
To compute marginal probabilities efficiently, a directed network must be converted into a computational tree structure known as a junction tree or clique tree. In their landmark paper introducing the HUGIN expert system shell, Andersen et al. detailed how causal networks are moralized and subsequently triangulated (adding edges to eliminate chordless cycles larger than three nodes). Triangulation ensures the graph is chordal, allowing it to be decomposed into a tree of cliques that maintains the Markov property. This allows global probability updates to be computed via local message-passing between cliques.
Shachter et al. similarly leverage this in Directed reduction algorithms and decomposable graphs, demonstrating that moralization combined with arc-reversal operations can systematically reduce complex directed influence diagrams into evaluation-ready, decomposable undirected forms.
Scaling Structure Learning and Deep Learning
The utility of moralization extends to structure learning and deep learning architectures, providing a way to bypass combinatorial bottlenecks and bridge disparate modeling frameworks.
Structure Learning and Decomposition
When learning the structure of a DAG from data, identifying v-structures is critical for pinning down causal directions. Geng et al. demonstrate in Decomposition of search for v-structures in DAGs that because conditional independencies map directly to separation properties in the moral graph, researchers can break down the global search for v-structures into smaller, localized subproblems on decomposed moral subgraphs, drastically reducing computational overhead.
Relational Models
In statistical relational learning, building purely undirected models like Markov Logic Networks (MLNs) often triggers an exponential explosion in the search space when dealing with continuous or multi-valued descriptive attributes. To solve this, Khosravi et al. introduce a "learn-and-join" approach in Structure Learning for Markov Logic Networks with Many Descriptive Attributes. They first learn a directed Bayesian network and then moralize it to synthesize the final undirected relational model. This hybrid strategy yields massive speedups while maintaining representational accuracy.
Graph Neural Networks
Moralization also plays a role in modern deep learning. Graph Convolutional Networks (GCNs) operate inherently on undirected graphs, passing messages symmetrically across neighborhoods. When researchers want to inject domain knowledge from a directed causal Bayesian network into a GCN, they face a structural mismatch.
In Dynamic Probabilistic Graph Convolution for Facial Action Unit Intensity Estimation, Song et al. resolve this by applying moralization to the directed causal network. By marrying the parent nodes before stripping the arrowheads, the structural integrity and conditional dependencies of the causal model are preserved, making the network fully compatible with undirected graph convolutional operations for feature extraction.
Extensions and Limitations
While moralization is highly effective for DAGs, extending it to cyclic graphs—where feedback loops exist—presents unique challenges. Pearl et al. show in Identifying Independencies in Causal Graphs with Feedback that directed cyclic graphs can still be mapped to undirected counterparts to prove that d-separation remains valid for discrete cyclic systems.
However, the transformation is not always cost-free. As Milan Studený observes in On Separation Criterion and Recovery Algorithm for Chain Graphs, applying moralization criteria to more flexible frameworks like chain graphs can sometimes obscure the original directed relationships, making it harder to directly read off certain independencies.
Despite these edge cases, the core mechanism of moralization—identifying where directed structures induce conditional dependencies and encoding them explicitly via undirected edges—remains one of the most powerful tools for translating between causal representations and computational architectures.
Key Foundational Work
Directed reduction algorithms and decomposable graphs (1990) — contributed 2 concept elements to this direction.
HUGIN - A Shell for Building Bayesian Belief Universes for Expert Systems (1989) — contributed 1 concept elements to this direction.
d-Separation: From Theorems to Algorithms (1989) — contributed 1 concept elements to this direction.