Sequential sampling of junction trees for decomposable graphs
From MaRDI portal
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.
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
Cites work
- An introduction to sequential Monte Carlo
- Asymptotic genealogies of interacting particle systems with an application to sequential Monte Carlo
- Bayesian learning of weakly structural Markov graph laws using sequential Monte Carlo methods
- Counting labelled chordal graphs
- Decomposable graphical Gaussian model determination
- Decomposition of maximum likelihood in mixed graphical interaction models
- Enumerating the decomposable neighbors of a decomposable graph under a simple perturbation scheme
- Equation of state calculations by fast computing machines
- Graph-Theoretic Solutions to Computational Geometry Problems
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- scientific article; zbMATH DE number 1134987 (Why is no real title available?)
- scientific article; zbMATH DE number 2106098 (Why is no real title available?)
- scientific article; zbMATH DE number 3324508 (Why is no real title available?)
- Inference in hidden Markov models.
- Markov chains for exploring posterior distributions. (With discussion)
- Monte Carlo sampling methods using Markov chains and their applications
- Particle Markov Chain Monte Carlo Methods
- Path storage in the particle filter
- Sampling decomposable graphs using a Markov chain on junction trees
- Sequential Monte Carlo Samplers
- Two methods for the generation of chordal graphs
- Unbiased approximation of posteriors via coupled particle Markov chain Monte Carlo
Cited in
(5)- Bayesian learning of weakly structural Markov graph laws using sequential Monte Carlo methods
- Incremental Junction Tree Inference
- Sampling decomposable graphs using a Markov chain on junction trees
- Graphical posterior predictive classification: Bayesian model averaging with particle Gibbs
- Parallel Sampling of Decomposable Graphs Using Markov Chains on Junction Trees
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)
