Efficient Exact Inference in Planar Ising Models

We give polynomial-time algorithms for the exact computation of lowest-energy states, worst margin violators, partition functions, and marginals in certain binary undirected graphical models. Our approach provides an interesting alternative to the well-known graph cut paradigm in that it does not impose any submodularity constraints; instead we require planarity to establish a correspondence with perfect matchings in an expanded dual graph. Maximum-margin parameter estimation for a boundary detection task shows our approach to be efficient and effective. A C++ implementation is available from http://nic.schraudolph.org/isinf/.

• Publication year

  2008

• Venue

  Neural Information Processing Systems

• Publication date

  2008-10-24

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  arXiv 0810.4401
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Simple MAX-CUT Algorithm for Planar Graphs.

  2009cited by this paper
• Exact ground states of large two-dimensional planar Ising spin glasses.

  2008cited by this paper
• Matching Kasteleyn Cities for Spin Glass Ground States

  2007cited by this paper
• Optimizing Binary MRFs via Extended Roof Duality

  2007influential reference
• Minimizing Nonsubmodular Functions with Graph Cuts-A Review

  2007cited by this paper
• A Stochastic Quasi-Newton Method for Online Convex Optimization

  2007cited by this paper
• Discriminative Random Fields

  2006cited by this paper
• Fast Computation of Graph Kernels

  2006cited by this paper
• Approximate inference using planar graph decomposition

  2006influential reference
• Accelerated training of conditional random fields with stochastic gradient methods

  2006cited by this paper
• From Fields to Trees

  2004cited by this paper
• Graph Embedding with Minimum Depth and Maximum External Face

  2003cited by this paper
• Discriminative Fields for Modeling Spatial Dependencies in Natural Images

  2003cited by this paper
• Understanding belief propagation and its generalizations

  2003cited by this paper
• Max-Margin Markov Networks

  2003cited by this paper
• Tree-based reparameterization framework for analysis of sum-product and related algorithms

  2003cited by this paper
• A new class of upper bounds on the log partition function

  2002cited by this paper
• What energy functions can be minimized via graph cuts?

  2002influential reference
• Implementation of O(nmlogn) weighted matchings in general graphs: the power of data structures

  2002cited by this paper
• Fast approximate energy minimization via graph cuts

  2001cited by this paper
• Exact MAP states and expectations from perfect sampling: Greig, porteous and seheult revisited

  2001cited by this paper
• Comparing the Mean Field Method and Belief Propagation for Approximate Inference in MRFs

  2001cited by this paper
• Implementation of O (nm log n) Weighted Matchings in General Graphs. The Power of Data Structures

  2000cited by this paper
• Cholesky-like Factorizations of Skew-Symmetric Matrices

  2000cited by this paper
• The Probablistic Method

  2000cited by this paper
• Computing Minimum-Weight Perfect Matchings

  1999influential reference
• A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results

  1992cited by this paper
• Exact Maximum A Posteriori Estimation for Binary Images

  1989cited by this paper
• On the limited memory BFGS method for large scale optimization

  1989cited by this paper
• Topological Graph Theory

  1987cited by this paper
• An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs

  1986cited by this paper
• On the Statistical Analysis of Dirty Pictures

  1986cited by this paper
• A Note on the Stable Decomposition of Skew-Symmetric Matrices

  1982cited by this paper
• On the computational complexity of Ising spin glass models

  1982cited by this paper
• Updating Quasi-Newton Matrices With Limited Storage

  1980cited by this paper
• On the ground states of the frustration model of a spin glass by a matching method of graph theory

  1980cited by this paper
• Algorithm 447: efficient algorithms for graph manipulation

  1973cited by this paper
• On the Dimer Solution of Planar Ising Models

  1966cited by this paper
• Paths, Trees, and Flowers

  1965cited by this paper
• Maximum matching and a polyhedron with 0,1-vertices

  1965cited by this paper
• Dimer Statistics and Phase Transitions

  1963cited by this paper
• Statistical Mechanics of Dimers on a Plane Lattice

  1961cited by this paper
• The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice

  1961cited by this paper
• Journal of Graph Algorithms and Applications on the Cutting Edge: Simplified O(n) Planarity by Edge Addition

  year unknowncited by this paper

• Assortment optimization given basket shopping behavior using the Ising model

  2025cites this paper
• Computing Classical Partition Functions: From Onsager and Kaufman to Quantum Algorithms

  2024cites this paper
• Stability of an Optical Neural Network Trained by the Maximum-Likelihood Algorithm

  2023cites this paper
• Exact Inference in High-order Structured Prediction

  2023cites this paper
• Inference and Optimization for Engineering and Physical Systems

  2022cites this paper
• A View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy

  2022cites this paper
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy

  2021cites this paper
• Classical algorithms for Forrelation

  2021cites this paper
• Fairness constraints can help exact inference in structured prediction

  2020cites this paper
• Discriminative learning for structured outputs and environments

  2019cites this paper
• A study and implementation of large-scale log-determinant computation to cloud

  2019cites this paper
• Tighter continuous relaxations for MAP inference in discrete MRFs: A survey

  2019cites this paper
• Next Neighbors Addition-Induced Change of 2D Ising Model Critical Parameters

  2019cites this paper
• Approximation of Edwards-Anderson Spin-Glass Model Density of States

  2019cites this paper
• Global Minimum Depth in Edwards-Anderson Model

  2019cites this paper
• Exact inference in structured prediction

  2019cites this paper
• A New Family of Tractable Ising Models

  2019cites this paper
• Prediction Approach for Ising Model Estimation

  2019cites this paper
• Tractable minor-free generalization of planar zero-field Ising models

  2019cites this paper
• Change in Density of States of 2D Ising Model when Next-Neighbor Interaction Is Introduced

  2019cites this paper
• Spectral Characteristics of a Finite 2D Ising Model

  2018cites this paper
• Dependence of Critical Temperature on Dispersion of Connections in 2D Grid

  2018cites this paper
• Dependence of Critical Parameters of 2D Ising Model on Lattice Size

  2018cites this paper
• Planar Ising-Spin Models in Probabilistic Machine Learning

  2018cites this paper
• Inference and Sampling of K33-free Ising Models

  2018cites this paper
• Investigation of Finite-Size 2D Ising Model with a Noisy Matrix of Spin-Spin Interactions

  2018cites this paper
• A Comparative Study of Local Search Algorithms for Correlation Clustering

  2017cites this paper
• Analytical expressions for a finite-size 2D Ising model

  2017cites this paper
• Fast spatial inference in the homogeneous Ising model

  2017cites this paper
• Inference in Sparse Graphs with Pairwise Measurements and Side Information

  2017cites this paper
• Approximations in the homogeneous Ising model

  2017cites this paper
• Visualizing the Uncertainty of Graph‐based 2D Segmentation with Min‐path Stability

  2017cites this paper
• Polynomial algorithm for exact calculation of partition function for binary spin model on planar graphs

  2016cites this paper
• Interactive Multilabel Image Segmentation via Robust Multilayer Graph Constraints

  2016cites this paper
• Stochastic Discrete Clenshaw-Curtis Quadrature

  2016cites this paper
• Multiple testing under dependence via graphical models

  2016cites this paper
• Spectral Inference Methods on Sparse Graphs: Theory and Applications

  2016cites this paper
• Spectral bounds for the Ising ferromagnet on an arbitrary given graph

  2016cites this paper
• Integration of PCA with a Novel Machine Learning Method for Reparameterization and Assisted History Matching Geologically Complex Reservoirs

  2015cites this paper
• Network Aided Classification and Detection of Data

  2015cites this paper
• Finding Textures in Sketches using Planar Ising Models

  2015cites this paper
• Large-scale log-determinant computation through stochastic Chebyshev expansions

  2015cites this paper
• Bethe Learning of Conditional Random Fields via MAP Decoding

  2015cites this paper
• Latent sentiment detection in Online Social Networks: A communications-oriented view

  2014cites this paper
• Exact solutions for discrete graphical models: multicuts and reduction techniques

  2014cites this paper
• Learning tree-structured approximations for conditional random fields

  2014cites this paper
• Methods for Inference in Graphical Models

  2014cites this paper
• ESSP: An Efficient Approach to Minimizing Dense and Nonsubmodular Energy Functions

  2014cites this paper
• Semi-Global Matching: A Principled Derivation in Terms of Message Passing

  2014cites this paper
• Cut, Glue, & Cut: A Fast, Approximate Solver for Multicut Partitioning

  2014cites this paper
• Statistical Methods for Genome-wide Association Studies and Personalized Medicine

  2014cites this paper
• Estimating the Partition Function of Graphical Models Using Langevin Importance Sampling

  2013cites this paper
• Approximate inference using unimodular graphs in dual decomposition

  2013cites this paper
• A new criterion for choosing planar subproblems in MAP-MRF inference

  2013cites this paper
• Towards Efficient and Exact MAP-Inference for Large Scale Discrete Computer Vision Problems via Combinatorial Optimization

  2013cites this paper
• Approximate Discriminative Training of Graphical Models

  2012cites this paper
• Fast Planar Correlation Clustering for Image Segmentation

  2012cites this paper
• Towards accurate structured output learning and prediction

  2012cites this paper
• Bayesian reasoning and machine learning

  2012cites this paper
• A Class of Random Fields on Complete Graphs with Tractable Partition Function

  2012cites this paper
• Partitioning planar graphs: a fast combinatorial approach for max-cut

  2012cites this paper
• Variational Approximate Inference Methods for Graphical Models

  2012cites this paper
• Graphical-model Based Multiple Testing under Dependence, with Applications to Genome-wide Association Studies

  2012cites this paper
• A polynomial-time algorithm for image segmentation using Ising models

  2011influential citation
• Generalized Fast Approximate Energy Minimization via Graph Cuts: Alpha-Expansion Beta-Shrink Moves

  2011cites this paper
• Structured Learning and Prediction in Computer Vision

  2011cites this paper
• Advances in Graph-Cut Optimization: Multi-Surface Models, Label Costs, and Hierarchical Costs

  2011cites this paper
• Accelerated Adaptive Markov Chain for Partition Function Computation

  2011influential citation
• Planar Decompositions and Cycle Constraints

  2011cites this paper
• Generalized Fast Approximate Energy Minimization via Graph Cuts: a-Expansion b-Shrink Moves

  2011cites this paper
• Planar Cycle Covering Graphs

  2011cites this paper
• Submodular decomposition framework for inference in associative Markov networks with global constraints

  2011cites this paper
• Tightening MRF Relaxations with Planar Subproblems

  2011cites this paper
• Revisiting the Linear Programming Relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction

  2010cites this paper
• Beyond trees: MRF inference via outer-planar decomposition

  2010cites this paper
• Non-rigid structure from locally-rigid motion

  2010cites this paper
• Approximate inference in graphical models using lp relaxations

  2010cites this paper
• Ising Graphical Model

  2010cites this paper
• Parallelizable Sampling of Markov Random Fields

  2010cites this paper
• Learning Planar Ising Models

  2010cites this paper
• Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching

  2010cites this paper
• Learning with structured data: applications to computer vision

  2009cites this paper
• Approximate Inference on Planar Graphs using Loop Calculus and Belief Propagation

  2009cites this paper
• Dynamic Planar-Cuts : Efficient Computation of Min-Marginals for OuterPlanar MRFs

  2009cites this paper
• Supplementary Material for the Paper “ Inference and Sampling of K 33-free Ising Models ” 1

  year unknowncites this paper