Marginal Pseudo-Likelihood Learning of Markov Network structures

Johan Pensar, Henrik Nyman, Juha Niiranen, Jukka Corander

TL;DR

This paper introduces Marginal Pseudo-Likelihood (MPL), a Bayesian framework for learning the structure of Markov networks without the restrictive assumption that the graph must be chordal. By marginalizing over nuisance parameters, the method provides automatic regularization, eliminating the need for manual tuning parameters while remaining computationally efficient enough for high-dimensional biological and physical systems.

What Problem Does This Paper Address?

Markov networks (undirected graphical models) are essential for modeling dependencies in complex systems, from protein folding to social networks. However, learning their structure from data is notoriously difficult.

The "gold standard" Bayesian approach requires calculating a normalizing constant known as the partition function. For general graphs, calculating this constant is NP-hard, forcing researchers to either assume the graph is "chordal" (triangulated) or use frequentist methods like $L_1$-regularized pseudo-likelihood. The former is often an unrealistic simplification of reality, while the latter requires a "tuning parameter" ($\lambda$) that must be painstakingly optimized via cross-validation—a process that is computationally expensive and prone to error with small datasets.

Methods

The authors propose a "best of both worlds" approach:

  1. Marginal Pseudo-Likelihood (MPL): Instead of the full likelihood, they use the pseudo-likelihood (the product of local conditional distributions). They treat the model parameters as "nuisance parameters" and marginalize them out using a Dirichlet prior. This results in an analytical scoring function that looks remarkably like the BDeu score used for Bayesian Networks but works for undirected graphs.
  2. Automatic Regularization: Because it is a Bayesian marginalization, the score naturally penalizes overly complex models. There is no $\lambda$ to tune.
  3. Two-Phase Optimization:
    • Phase 1 (Prescan): A local search (greedy hill climbing) identifies the "Markov blanket" for each node independently. This can be done in parallel.
  4. Phase 2 (Global): The local results are stitched together into a consistent undirected graph. The authors provide an exact solution using Pseudo-Boolean Optimization (PBO) for smaller graphs and a Greedy Hill Climbing (HC) heuristic for high-dimensional ones.

Datasets

The authors evaluated MPL using three distinct types of data:

  • Synthetic Networks: Scalable models (64 to 512 variables) built from four structural components: Grid, Hub, Loop, and Clique.
  • Moralized Benchmarks: Standard Bayesian Network benchmarks (Alarm, Insurance, Hailfinder, Barley) converted into undirected Markov networks.
  • Real-World Genomic Data: 1,000 aligned DNA sequences of Mycobacterium tuberculosis (589 variables) to identify long-distance genetic associations.

Key Insights and Ideas

  • The "Aha!" Moment: By applying Bayesian marginalization to the pseudo-likelihood rather than the full likelihood, you bypass the intractable partition function entirely while retaining the "automatic" complexity control that Bayesian methods are famous for.
  • Parallelism by Design: Because the pseudo-likelihood factorizes variable-wise, the most difficult part of the structure learning (finding local neighborhoods) can be distributed across multiple CPU cores.
  • Conservative Learning: MPL tends to be more conservative than standard Maximum Likelihood. It has a lower False Positive rate, meaning it is less likely to "hallucinate" edges that aren't there—a vital trait for scientific discovery where follow-up experiments are expensive.

Key Results

  • Accuracy: In synthetic tests, MPL consistently achieved lower Hamming distances (fewer total errors) than competing methods like Conditional Mutual Information (CMI) and $L_1$-regularized logistic regression (L1LR).
  • Robustness: Unlike L1LR, which performed poorly if the tuning parameter was slightly off, MPL performed "highly satisfactorily" out of the box without any parameter tweaking.
  • Scalability: The greedy hill climbing optimization reached the global optimum (verified by the exact PBO solver) in the vast majority of cases, proving that the heuristic is reliable for large-scale systems.
  • Biological Discovery: On the M. tuberculosis data, MPL successfully mapped a sparse network of genomic linkages, identifying long-distance associations consistent with the known low recombination rate of the bacterium.

Limitations and Future Work

The authors note that MPL is slightly less "data efficient" than the true (but intractable) Marginal Likelihood. Specifically, it struggles more than the full ML when the true graph contains "hub nodes" (nodes with a very high number of neighbors) and the sample size is small.

Future research directions suggested include:

  • Developing more sophisticated priors to further improve data efficiency.
  • Extending the MPL framework to handle continuous data (the current paper focuses on discrete variables).
  • Exploring the use of MPL in hybrid models that combine directed and undirected edges.

Summary updated

Abstract

Undirected graphical models known as Markov networks are popular for a wide variety of applications ranging from statistical physics to computational biology. Traditionally, learning of the network structure has been done under the assumption of chordality which ensures that efficient scoring methods can be used. In general, non-chordal graphs have intractable normalizing constants which renders the calculation of Bayesian and other scores difficult beyond very small-scale systems. Recently, there has been a surge of interest towards the use of regularized pseudo-likelihood methods for structural learning of large-scale Markov network models, as such an approach avoids the assumption of chordality. The currently available methods typically necessitate the use of a tuning parameter to adapt the level of regularization for a particular dataset, which can be optimized for example by cross-validation. Here we introduce a Bayesian version of pseudo-likelihood scoring of Markov networks, which enables an automatic regularization through marginalization over the nuisance parameters in the model. We prove consistency of the resulting MPL estimator for the network structure via comparison with the pseudo information criterion. Identification of the MPL-optimal network on a prescanned graph space is considered with both greedy hill climbing and exact pseudo-Boolean optimization algorithms. We find that for reasonable sample sizes the hill climbing approach most often identifies networks that are at a negligible distance from the restricted global optimum. Using synthetic and existing benchmark networks, the marginal pseudo-likelihood method is shown to generally perform favorably against recent popular inference methods for Markov networks.
BibTeX
@inproceedings{pensar2016marginal,
  author = {Johan Pensar and Henrik Nyman and Juha Niiranen and Jukka Corander},
  title = {{Marginal Pseudo-Likelihood Learning of Markov Network structures}},
  booktitle = {Bayesian},
  year = {2016},
  doi = {10.1214/16-ba1032},
}
Figure