Stratified Graphical Models - Context-Specific Independence in Graphical Models

Henrik Nyman, Johan Pensar, Timo Koski, Jukka CoranderBayesian 2014 · DOI

Abstract

Theory of graphical models has matured over more than three decades to provide the backbone for several classes of models that are used in a myriad of applications such as genetic mapping of diseases, credit risk evaluation, reliability and computer security. Despite their generic applicability and wide adoption, the constraints imposed by undirected graphical models and Bayesian networks have also been recognized to be unnecessarily stringent under certain circumstances. This observation has led to the proposal of several generalizations that aim at more relaxed constraints by which the models can impose local or context-specific dependence structures. Here we consider an additional class of such models, termed stratified graphical models. We develop a method for Bayesian learning of these models by deriving an analytical expression for the marginal likelihood of data under a specific subclass of decomposable stratified models. A non-reversible Markov chain Monte Carlo approach is further used to identify models that are highly supported by the posterior distribution over the model space. Our method is illustrated and compared with ordinary graphical models through application to several real and synthetic datasets.

Introduction: Beyond All-or-Nothing Independence

In traditional graphical models, such as Bayesian Networks or Markov Random Fields, conditional independence is an "all-or-nothing" property. If variables $X$ and $Y$ are independent given $Z$, this relationship must hold for every possible value of $Z$. However, real-world data often exhibits more nuanced dependencies. For instance, a person’s smoking habits might only influence their blood pressure in the presence of a specific genetic marker. Standard models are often too rigid to capture these "context-specific" dependencies, leading to models that are either over-parameterized or fail to represent local structures accurately.

Methods: Stratified Graphical Models (SGMs)

To address these limitations, the authors introduce Stratified Graphical Models (SGMs). In an SGM, edges in an undirected graph can be "labeled" with a stratum—a specific subset of variable outcomes where the connected variables become independent.

Conceptual illustration of Stratified Graphical Models. (a) shows a standard graph, (b) introduces a context-specific label $X_1=1$ on an edge, and (c) shows full independence.

Key technical contributions include:

  • Decomposable SGMs: The framework focuses on a subclass where the underlying graph is decomposable (chordal) and labels follow specific rules to maintain mathematical tractability.
  • Analytical Marginal Likelihood: The authors derived a closed-form expression for the marginal likelihood of data given a decomposable SGM. This avoids the need for computationally expensive simulations during model scoring.
  • Non-Reversible MCMC: To navigate the vast space of possible graphs and label combinations, a non-reversible Markov Chain Monte Carlo algorithm is used to identify models with high posterior probability.

Evaluation and Key Insights

The approach was tested on synthetic data and real-world datasets, including coronary heart disease risk factors, Finnish election data, and North American plant distributions.

Examples of stratified structures on a 5-node clique. Labels on edges indicate specific contexts (combinations of variable values) where independence occurs.

Several key insights emerged:

  • Parsimony: SGMs can describe complex dependencies with fewer parameters. In the election dataset, the best SGM used 324 free parameters versus 368 for the best standard model, while providing a superior fit.
  • Interpretability: Labeled edges make the dependence structure "readable," allowing researchers to see exactly which conditions trigger independence.
  • Data Requirements: Synthetic tests showed that as clique size increases, the data required to reliably identify correct labels grows exponentially. For a 5-variable clique, even 100,000 observations only yielded a 50% success rate in exact label recovery.
  • Error Detection: In the plant dataset, the SGM's structure helped identify a data entry error where "Alabama" and "Alberta" had been swapped.

Conclusion

Stratified Graphical Models offer a powerful extension to traditional graphical modeling by allowing for context-specific independence. While currently limited to decomposable graphs and primarily binary data, the derivation of an analytical marginal likelihood represents a significant step forward for efficient Bayesian learning of these complex structures. Future work will look into non-decomposable graphs and more efficient search strategies for large-scale cliques.

Summary updated

Abstract

Theory of graphical models has matured over more than three decades to provide the backbone for several classes of models that are used in a myriad of applications such as genetic mapping of diseases, credit risk evaluation, reliability and computer security. Despite their generic applicability and wide adoption, the constraints imposed by undirected graphical models and Bayesian networks have also been recognized to be unnecessarily stringent under certain circumstances. This observation has led to the proposal of several generalizations that aim at more relaxed constraints by which the models can impose local or context-specific dependence structures. Here we consider an additional class of such models, termed stratified graphical models. We develop a method for Bayesian learning of these models by deriving an analytical expression for the marginal likelihood of data under a specific subclass of decomposable stratified models. A non-reversible Markov chain Monte Carlo approach is further used to identify models that are highly supported by the posterior distribution over the model space. Our method is illustrated and compared with ordinary graphical models through application to several real and synthetic datasets.
BibTeX
@inproceedings{nyman2014stratified,
  author = {Henrik Nyman and Johan Pensar and Timo Koski and Jukka Corander},
  title = {{Stratified Graphical Models - Context-Specific Independence in Graphical Models}},
  booktitle = {Bayesian},
  year = {2014},
  doi = {10.1214/14-ba882},
}
Figure