## Abstract

We present a new family of zero-field Ising models over N binary variables/spins obtained by consecutive 'gluing' of planar and O(1)-sized components and subsets of at most three vertices into a tree. The polynomial time algorithm of the dynamic programming type for solving exact inference (computing partition function) and exact sampling (generating i.i.d. samples) consists of sequential application of an efficient (for planar) or brute-force (for O(1)-sized) inference and sampling to the components as a black box. To illustrate the utility of the new family of tractable graphical models, we first build a polynomial algorithm for inference and sampling of zero-field Ising models over K 33-minor-free topologies and over K 5-minor-free topologies - both of which are extensions of the planar zero-field Ising models - which are neither genus- nor treewidth-bounded. Second, we empirically demonstrate an improvement in the approximation quality of the NP-hard problem of inference over the square-grid Ising model in a node-dependent nonzero 'magnetic' field.

Original language | English (US) |
---|---|

Article number | 124007 |

Journal | Journal of Statistical Mechanics: Theory and Experiment |

Volume | 2020 |

Issue number | 12 |

DOIs | |

State | Published - Dec 21 2020 |

Externally published | Yes |

## Keywords

- analysis of algorithms
- inference of graphical models
- statistical inference

## ASJC Scopus subject areas

- Statistical and Nonlinear Physics
- Statistics and Probability
- Statistics, Probability and Uncertainty