Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs

DOI10.1162/NECO_a_00441zbMath1418.62232OpenAlexW2135111563WikidataQ44652652 ScholiaQ44652652MaRDI QIDQ5378213

Frederik Eaton, Zoubin Ghahramani

Publication date: 12 June 2019

Published in: Neural Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1162/neco_a_00441

zbMATH Keywords

spectral reductionclass of binary pairwise factor graphsreductions for inference

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10)

Uses Software

• LibDAI

Cites Work

• The complexity of computing the permanent
• Pseudo-Boolean optimization
• Inapproximability of the Tutte polynomial
• The complexity of partition functions
• The computational complexity of probabilistic inference using Bayesian belief networks
• Über eine Eigenschaft der ebenen Komplexe
• Belief propagation and loop series on planar graphs
• The statistics of dimers on a lattice
• Loop series for discrete statistical models on graphs
• Counting independent sets up to the tree threshold
• New Graph Polynomials from the Bethe Approximation of the Ising Partition Function
• CCCP Algorithms to Minimize the Bethe and Kikuchi Free Energies: Convergent Alternatives to Belief Propagation
• Holographic Algorithms
• The Complexity of Weighted Boolean #CSP
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• The Complexity of Enumeration and Reliability Problems
• Planar Formulae and Their Uses
• Quantum Complexity Theory
• Factor graphs and the sum-product algorithm
• Linear Response Algorithms for Approximate Inference in Graphical Models
• Message Passing for Maximum Weight Independent Set
• Survey propagation: An algorithm for satisfiability
• Computational Complexity
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• An algebra of bayesian belief universes for knowledge‐based systems
• A Theorem on Planar Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item