Segregated Graphs and Marginals of Chain Graph Models

Ilya ShpitserNeurIPS 2015 · OpenReview

Introduction: The Challenge of Hidden Variables in Complex Networks

In statistics and machine learning, we frequently rely on graphical models to map out relationships between variables. Bayesian Networks (directed graphs) are typically used to model asymmetric, cause-and-effect relationships, while Markov Random Fields (undirected graphs) model symmetric relationships, such as pixels in an image or social network ties. Chain Graphs offer the "best of both worlds," combining directed and undirected edges to represent systems with both causal and symmetric components.

However, a significant challenge arises when some variables in a chain graph are "hidden" or unobserved. Marginalizing out (ignoring) these hidden variables creates complex dependencies that standard chain graphs cannot easily represent. While tools like "ordinary Markov models" exist to handle hidden variables in purely causal directed acyclic graphs (DAGs), a similarly well-behaved "supermodel" for chain graphs has been missing.

Examples of graphs modeling causal interference between subjects.

This paper fills that gap by introducing a framework specifically targeted at applications like causal interference—scenarios where the symmetry of social or biological interactions meets the asymmetry of medical treatments (e.g., where one subject's treatment affects another subject's outcome).

Methods: Introducing Segregated Graphs (SGs)

To solve the marginalization problem in chain graphs, the author introduces Segregated Graphs (SGs). SGs are a new class of mixed graphical models containing three types of edges: directed ($\rightarrow$), undirected (—), and bidirected ($\leftrightarrow$).

The defining characteristic—the "trick"—of an SG is a strict structural constraint: undirected edges and bidirected edges are never allowed to meet at a single vertex. This segregation ensures the graphs remain mathematically tractable and factorizable.

Key methodological contributions include:

  • The s-separation criterion: A global Markov property that determines which variables are conditionally independent of each other based purely on the graph's structure.
  • Latent Projection: A formal procedure to transform a complex chain graph with hidden variables into a simpler SG. This projection preserves all relevant independence constraints among the observed variables.
  • Segregated Factorization: A method to break down the joint probability distribution into smaller "kernels" or pieces. For positive distributions, this factorization is mathematically equivalent to the graph's Markov properties.
Latent projection of a chain graph with a hidden variable U.

Experimental Validation and Key Insights

The paper validates the SG framework using simulated datasets modeling a placebo-controlled vaccination trial. The scenario involves mother/child pairs where the child is vaccinated. "Interference" occurs because the child's vaccination status affects the mother's health outcome, even though the mother wasn't vaccinated.

The underlying model consists of a 5-variable system ($A, W, B_1, Y_1, Y_2$) plus a 15-valued hidden variable ($U$) representing unobserved health status. By generating 1,000 datasets (5,000 samples each), the author tested whether the SG could accurately recover the underlying distribution's properties without explicitly modeling $U$.

Key Results

  • Accurate Model Fit: The deviances of the fitted SG models closely followed a $\chi^2$ distribution with 14 degrees of freedom. This confirms that the SG correctly captured the constraints of the marginal distribution induced by the hidden variable.
  • Parameter Encoding: The SG successfully encoded interaction parameters (the strength of interference). As the interaction strength in the "true" model changed, the parameters in the SG shifted predictably, demonstrating that SGs are practical tools for actual estimation, not just theoretical constructs.
  • Tractability via Segregation: By forbidding undirected and bidirected edges from touching, the likelihood function decomposes into distinct "districts" and "blocks." This allows researchers to use existing, efficient fitting algorithms rather than inventing entirely new ones.
  • Symmetry Breaking: When projecting a symmetric relationship (undirected edge) through a hidden variable, the SG framework might replace that undirected edge with directed ones. While this visually "breaks the symmetry," it mathematically preserves the correct independence constraints.

Limitations and Future Work

While Segregated Graphs offer a powerful new tool, the author notes a few limitations. First, the directed edges in an SG do not always have a straightforward causal interpretation; because the latent projection process might replace undirected edges with directed ones to satisfy independence constraints, arrows cannot always be read as direct physical causes.

Additionally, the SG representing a marginal model is not necessarily unique—different sequences of "projecting out" variables might lead to different-looking graphs that represent the same statistical model. Finally, while the theory is general, the specific fitting algorithms discussed are tailored toward discrete state spaces. Extending these practical fitting procedures to high-dimensional continuous data remains an exciting area for future research.

Summary updated

Abstract

Bayesian networks are a popular representation of asymmetric (for example causal) relationships between random variables. Markov random fields (MRFs) are a complementary model of symmetric relationships used in computer vision, spatial modeling, and social and gene expression networks. A chain graph model under the Lauritzen-Wermuth-Frydenberg interpretation (hereafter a chain graph model) generalizes both Bayesian networks and MRFs, and can represent asymmetric and symmetric relationships together.As in other graphical models, the set of marginals from distributions in a chain graph model induced by the presence of hidden variables forms a complex model. One recent approach to the study of marginal graphical models is to consider a well-behaved supermodel. Such a supermodel of marginals of Bayesian networks, defined only by conditional independences, and termed the ordinary Markov model, was studied at length in (Evans and Richardson, 2014).In this paper, we show that special mixed graphs which we call segregated graphs can be associated, via a Markov property, with supermodels of a marginal of chain graphs defined only by conditional independences. Special features of segregated graphs imply the existence of a very natural factorization for these supermodels, and imply many existing results on the chain graph model, and ordinary Markov model carry over. Our results suggest that segregated graphs define an analogue of the ordinary Markov model for marginals of chain graph models.
BibTeX
@inproceedings{shpitser2015segregated,
  author = {Ilya Shpitser},
  title = {{Segregated Graphs and Marginals of Chain Graph Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=H1Z19w-ubS},
}
Figure