Source-linked AI summary
Structure Learning in Graphical Modeling
Mathias Drton, Marloes H. Maathuis
TL;DR
Structure learning asks how to estimate graphs summarizing dependence structures from data, motivated in part by biological network reconstruction. The review surveys methods for undirected and directed graphical models and extensions involving latent variables and heterogeneous data. It reports detection of known interactions in an E. coli example while noting important assumptions and scope limits.
Problem
Structure learning must estimate graphs that summarize dependence structures in data, with applications including reconstruction of gene regulatory networks.
Method
The review surveys graphical-lasso and neighborhood-selection methods for undirected models, PC and score-based searches for directed models, and extensions for latent variables and heterogeneous data.
Results
In an E. coli example, neighborhood selection estimated 352 edges including 24 of 124 known interactions, with random-selection probability about 1.5 × 10−4.
Takeaways & Limitations
Graphical-model structure learning provides a framework for estimating dependency networks across undirected, directed, latent-variable, and heterogeneous-data settings.
Takeaways & Limitations
PC consistency relies on the underlying DAG being a perfect map, an assumption that can be restrictive.
Abstract
from arXiv · showhide
A graphical model is a statistical model that is associated to a graph whose nodes correspond to variables of interest. The edges of the graph reflect allowed conditional dependencies among the variables. Graphical models admit computationally convenient factorization properties and have long been a valuable tool for tractable modeling of multivariate distributions. More recently, applications such as reconstructing gene regulatory networks from gene expression data have driven major advances in structure learning, that is, estimating the graph underlying a model. We review some of these advances and discuss methods such as the graphical lasso and neighborhood selection for undirected graphical models (or Markov random fields), and the PC algorithm and score-based search methods for directed graphical models (or Bayesian networks). We further review extensions that account for effects of latent variables and heterogeneous data sources.
1. Introduction
This review introduces structure learning as estimating a graph that summarizes dependencies in data, then surveys graphical-model methods and applications including gene-network reconstruction.
- Motivation: Structure learning estimates a graph that summarizes the dependence structure in a data set.
- Graphical models: Graphical models associate variables with graph nodes and encode conditional independencies through suitably blocked paths.
- Graphical models: Undirected and directed graphs can represent Markov chains through different conditional-independence structures.
- Graphical models: Factorizations make high-dimensional joint distributions more efficient to store and compute.For a binary Markov chain, a joint distribution with 2^m−1 dimensions is determined by 2^m−1 parameters.
- Applications: Gene-expression applications have driven advances in structure learning, including an estimated conditional-independence graph for 87 E. coli transcription factors.The estimate had 352 edges and included 24 of 124 known interactions; a random selection would achieve at least 24 with probability about 1.5 × 10−4.
- Scope: The review covers undirected and directed models, latent variables, heterogeneous data sources, and selected structure-learning methods.Bayesian inference, dynamic graphical models, active learning, and other topics are explicitly outside its scope.
2. Basic Concepts in Graphical Modeling
Graphical-model semantics connect graph separation, conditional independence, and density factorization. The section develops these ideas for undirected and directed models and explains their implications for estimation.
- Undirected graphical models: In an undirected graph, separation encodes conditional independence, while the local Markov property conditions each variable on its neighbors.
- Undirected graphical models: The Hammersley–Clifford theorem equates pairwise Markov structure and factorization for positive densities.
- Undirected graphical models: For Gaussian models, absent edges correspond to zero entries in the inverse covariance matrix.
- Undirected graphical models: The Gaussian graphical-model MLE maximizes log-likelihood subject to positive definiteness and zeros over non-edges, but singular sample covariance can make the likelihood unbounded.
- Directed graphical models: DAGs use d-separation and local parent-based structure, with global and local Markov properties equivalent to factorization under the stated density assumptions.
- Directed graphical models: A perfect map requires graph-implied and distributional conditional independencies to coincide, an assumption important for structure-learning methods.
3. Learning Undirected Graphical Models
Undirected graphical-model learning ranges from efficient tree methods to heuristic search and penalized estimators for general graphs. These methods exploit factorization, local computations, or sparsity, with trade-offs involving computational complexity, tuning, and estimator consistency.
- 3.1. Chow-Liu Trees and Forests: Tree-structured distributions can be learned efficiently by finding a maximum-likelihood tree, equivalently a maximum spanning tree weighted by empirical mutual information.Kruskal’s algorithm adds edges in decreasing mutual-information order while skipping cycle-forming edges; stopping after k edges yields a maximum-likelihood k-edge forest.
- 3.1. Chow-Liu Trees and Forests: The Chow-Liu approach extends beyond categorical data by estimating bivariate marginals and using their mutual informations as spanning-tree weights.For bivariate normal marginals, mutual information is a function of squared empirical correlation, so absolute correlations can serve as weights.
- 3.2. Greedy Search: For general graphs, likelihood or information-criterion optimization is computationally hard, motivating greedy search with local edge-addition and edge-removal computations.Clique-sum decompositions make likelihood-ratio calculations local, while neighborhood-selection formulations avoid iterative MLE computation for nondecomposable graphs.
- 3.2. Greedy Search: Clique-sum decompositions factorize densities through prime components and separating sets, enabling likelihood-ratio calculations using only variables in the relevant clique.For decomposable graphs, Gaussian and categorical models additionally admit closed-form MLEs based on estimated marginal distributions.
- 3.3. ℓ1 Penalization: Neighborhood selection estimates each node’s neighborhood through local prediction or variable selection, whereas graphical lasso estimates a sparse inverse covariance structure using ℓ1 regularization.The graphical-lasso penalty induces sparsity in the estimated precision matrix, and edges correspond to its nonzero off-diagonal entries.
- 3.4. Neighborhood Selection: Under ℓ1 regularization, neighborhood selection and graphical lasso require different irrepresentability conditions, and consistency of one need not imply consistency of the other.The review cites Gaussian examples where neighborhood selection is consistent whenever graphical lasso is consistent, but not conversely.
4. Learning Directed Graphical Models
Directed graphical-model structure learning targets DAGs or their CPDAGs, using score-based search, conditional-independence tests, and hybrid methods under assumptions such as perfect-map structure.
- Problem: Directed structure learning often targets the CPDAG because the DAG is generally not identifiable from the distribution alone.Methods therefore recover a Markov equivalence class rather than necessarily one unique DAG.
- Score-Based Search: Score-based methods optimize a decomposable score, while exact search is difficult because DAG spaces are large and must satisfy acyclicity.Dynamic programming, integer linear programming, and branch-and-bound methods provide different exact-search strategies.
- Score-Based Search: GES greedily adds and removes edges in CPDAG space and is asymptotically consistent when its score is decomposable, score-equivalent, and consistent.Its global-optimum guarantee holds with probability converging to 1 as n →∞ under those conditions.
- Score-Based Search: GES can require exponentially many score evaluations, although polynomial-time behavior is available for sparse graphs with an appropriate backward phase.The edge-operation count is polynomial, but naive score evaluation can remain exponential in |V |.
- Constraint-Based Methods: The PC algorithm learns the skeleton by progressively testing conditional independencies over adjacency subsets, then orients v-structures and additional edges.For bounded-degree graphs, its running time is polynomial in the number of variables but exponential in the degree.
- Constraint-Based and Hybrid Methods: PC consistency relies on the underlying DAG being a perfect map, an assumption that can be restrictive; hybrid methods likewise face consistency challenges.Adaptively Restricted GES was shown to be consistent in classical and high-dimensional settings after restricted hybrids were shown inconsistent.
5. Latent Variables
Latent variables complicate structure learning because observed-variable distributions may not retain a DAG representation or causal interpretation. The review describes sparse-plus-low-rank methods for undirected models and mixed-graph approaches for directed models.
- Latent variables are unobserved variables that can induce observed correlations or represent specific unobserved quantities of interest.
- 5.1. Low-Rank Structure in Undirected Graphical Models: In Gaussian undirected models, marginalizing latent variables yields a sparse observed-graph component plus a low-rank component in the inverse covariance.The low-rank component has rank at most the number of latent variables.
- 5.1. Low-Rank Structure in Undirected Graphical Models: Penalized maximum likelihood estimates the sparse and low-rank components using ℓ1 and trace/nuclear norm penalties.The resulting optimization problem is convex.
- 5.1. Low-Rank Structure in Undirected Graphical Models: Under identifiability conditions, the estimated sparse pattern and low-rank rank consistently estimate the observed subgraph and number of hidden variables.The theory allows the number of observed variables to be roughly as large as the sample size.
- 5.2. Latent Variables in Directed Graphical Models: For directed models, marginalizing latent variables can prevent any DAG from encoding the observed conditional independencies or preserve independencies while destroying causal interpretation.One example has no perfect-map DAG after marginalization; another yields a DAG suggesting a nonexistent causal path.
- 5.2. Latent Variables in Directed Graphical Models: Mixed graphs, including maximal ancestral graphs, represent observed-variable dependence structures arising from latent-variable DAGs without explicitly modeling the latent variables.FCI generalizes the PC algorithm for constraint-based learning with latent variables.
- 5.2. Latent Variables in Directed Graphical Models: Maximal ancestral graphs represent all marginal conditional independencies but cannot generally represent equality and inequality constraints such as Verma constraints.Nested Markov models and mDAGs are proposed to represent additional constraints.
6. Heterogeneous Data
Heterogeneous data arise across populations, experimental conditions, organisms, disorders, and time. The review describes penalties and covariance-estimation strategies that learn shared, similar, differing, or time-varying graphical structure.
- Heterogeneous observations motivate learning graphical structures for subpopulations or graphs that depend on covariates.Examples include gene-expression studies across organisms or conditions and brain networks across neurological disorders.
- 6.1. Multiple Populations: Extensions of the graphical lasso estimate conditional independence graphs for several related Gaussian populations while encouraging shared structure.The inverse covariances are reparametrized as Ki,vw = θvwγi,vw.
- 6.1. Multiple Populations: Vector ℓ1 penalties can make edges simultaneously absent across populations, while fused lasso penalties encourage pairwise-similar edge patterns.Variants address positive and negative signals, unequal population relatedness, and direct estimation of graph differences.
- 6.2. Time-Varying Graphs: Time-varying structure can be learned using graphical-lasso estimates based on kernel-weighted covariance matrices or fused lasso penalties.Matrix/tensor-normal models offer another approach when one dimension represents time.
- 6.3. Directed Graphical Models: Dynamic Bayesian networks model temporal dependencies in directed graphical models and connect naturally to vector-autoregressive processes.A detailed discussion is beyond the scope of the review.
- 6.3. Directed Graphical Models: Directed structure learning can exploit data from known experimental conditions, with some methods allowing cycles or latent variables.These approaches generally assume i.i.d. observations within the various conditions.
7. Discussion
The review highlights rapid development in high-dimensional structure learning, including regularization, search, conditional-independence testing, and extensions for latent variables. It also identifies uncertainty assessment and cyclic causal structure as continuing challenges.
- Recent structure-learning work has been stimulated by gene-expression applications and increasingly focuses on high-dimensional problems.
- The review emphasizes ℓ1-regularization, greedy search, conditional-independence tests, and extensions for latent variables as major developments.
- Bayesian methods naturally provide uncertainty assessment, while frequentist methods for high-dimensional structure estimates are still being developed.
- The discussion of directed models is limited to acyclic graphs, whereas effectively learning cyclic cause-effect relationships from high-dimensional observational data remains difficult.Some feedback can be represented through linear structural equation models, but these models generally cannot be described solely by conditional independence.