Sequential sampling of junction trees for decomposable graphs

DOI10.1007/S11222-022-10113-2zbMATH Open1496.62019arXiv1806.00584OpenAlexW2806222559MaRDI QIDQ2080362FDOQ2080362

Authors: Jimmy Olsson, Tatjana Pavlenko, Felix L. Rios 

Publication date: 7 October 2022

Published in: Statistics and Computing (Search for Journal in Brave)

Abstract: The junction-tree representation provides an attractive structural property for organizing a decomposable graph. In this study, we present two novel stochastic algorithms, which we call the junction-tree expander and junction-tree collapser for sequential sampling of junction trees for decomposable graphs. We show that recursive application of the junction-tree expander, expanding incrementally the underlying graph with one vertex at a time, has full support on the space of junction trees with any given number of underlying vertices. On the other hand, the junction-tree collapser provides a complementary operation for removing vertices in the underlying decomposable graph of a junction tree, while maintaining the junction tree property. A direct application of our suggested algorithms is demonstrated in a sequential-Monte-Carlo setting designed for sampling from distributions on spaces of decomposable graphs. Numerical studies illustrate the utility of the proposed algorithms for combinatorial computations on decomposable graphs and junction trees. All the methods proposed in the paper are implemented in the Python library trilearn.

Full work available at URL: https://arxiv.org/abs/1806.00584

Recommendations

• Sampling decomposable graphs using a Markov chain on junction trees
• The tree structure of graphs for various graphical models
• Enumerating the decomposable neighbors of a decomposable graph under a simple perturbation scheme
• Bayesian learning of weakly structural Markov graph laws using sequential Monte Carlo methods
• Decomposable graphical Gaussian model determination

zbMATH Keywords

sequential Monte Carlographical modelsrandom graphsdecomposable graphsjunction trees

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Monte Carlo methods (65C05) Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• Sequential Monte Carlo Samplers
• Markov chains for exploring posterior distributions. (With discussion)
• Inference in hidden Markov models.
• Decomposition of maximum likelihood in mixed graphical interaction models
• Title not available (Why is that?)
• Particle Markov Chain Monte Carlo Methods
• Title not available (Why is that?)
• Monte Carlo sampling methods using Markov chains and their applications
• Equation of state calculations by fast computing machines
• An introduction to sequential Monte Carlo
• Decomposable graphical Gaussian model determination
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two methods for the generation of chordal graphs
• Enumerating the decomposable neighbors of a decomposable graph under a simple perturbation scheme
• Counting labelled chordal graphs
• Sampling decomposable graphs using a Markov chain on junction trees
• Path storage in the particle filter
• Graph-Theoretic Solutions to Computational Geometry Problems
• Asymptotic genealogies of interacting particle systems with an application to sequential Monte Carlo
• Unbiased approximation of posteriors via coupled particle Markov chain Monte Carlo
• Bayesian learning of weakly structural Markov graph laws using sequential Monte Carlo methods

Cited In (4)

• Sampling decomposable graphs using a Markov chain on junction trees
• Incremental Junction Tree Inference
• Graphical posterior predictive classification: Bayesian model averaging with particle Gibbs
• Bayesian learning of weakly structural Markov graph laws using sequential Monte Carlo methods

This page was built for publication: Sequential sampling of junction trees for decomposable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2080362)