Contextual Symmetries in Probabilistic Graphical Models

An important approach for efficient inference in probabilistic graphical models exploits symmetries among objects in the domain. Symmetric variables (states) are collapsed into meta-variables (meta-states) and inference algorithms are run over the lifted graphical model instead of the flat one. Our paper extends existing definitions of symmetry by introducing the novel notion of contextual symmetry. Two states that are not globally symmetric, can be contextually symmetric under some specific assignment to a subset of variables, referred to as the context variables. Contextual symmetry subsumes previous symmetry definitions and can rep resent a large class of symmetries not representable earlier. We show how to compute contextual symmetries by reducing it to the problem of graph isomorphism. We extend previous work on exploiting symmetries in the MCMC framework to the case of contextual symmetries. Our experiments on several domains of interest demonstrate that exploiting contextual symmetries can result in significant computational gains.

• Publication year

  2016

• Venue

  International Joint Conference on Artificial Intelligence

• Publication date

  2016-06-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1606.09594
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Journal of Symbolic Computation

  2022cited by this paper
• Lifted Symmetry Detection and Breaking for MAP Inference

  2015cited by this paper
• Graph isomorphism in quasipolynomial time [extended abstract]

  2015cited by this paper
• Approximate Lifting Techniques for Belief Propagation

  2014cited by this paper
• Efficient Lifting of MAP LP Relaxations Using k-Locality

  2014cited by this paper
• Scaling-up Importance Sampling for Markov Logic Networks

  2014cited by this paper
• Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference

  2014cited by this paper
• Lifted Probabilistic Inference for Asymmetric Graphical Models

  2014cited by this paper
• Lifted MAP Inference for Markov Logic Networks

  2014cited by this paper
• Practical graph isomorphism, II

  2013cited by this paper
• On the Complexity and Approximation of Binary Evidence in Lifted Inference

  2013cited by this paper
• RockIt: Exploiting Parallelism and Symmetry for MAP Inference in Statistical Relational Models

  2013influential reference
• On Lifting the Gibbs Sampling Algorithm

  2012cited by this paper
• Automorphism Groups of Graphical Models and Lifted Variational Inference

  2012influential reference
• Proceedings of the 49th Annual Design Automation Conference

  2012cited by this paper
• Markov Chains on Orbits of Permutation Groups

  2012cited by this paper
• Advances in Lifted Importance Sampling

  2012cited by this paper
• Probabilistic theorem proving

  2011cited by this paper
• Lifted graphical models: a survey

  2011cited by this paper
• Lifted Inference Seen from the Other Side : The Tractable Features

  2010cited by this paper
• Counting Belief Propagation

  2009cited by this paper
• Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning

  2009influential reference
• Markov Logic: An Interface Layer for Artificial Intelligence

  2009cited by this paper
• Lifted First-Order Belief Propagation

  2008influential reference
• Faster symmetry discovery using sparsity of symmetries

  2008cited by this paper
• Groupoids and Conditional Symmetry

  2007cited by this paper
• General Symmetry Breaking Constraints

  2006cited by this paper
• Markov logic networks

  2006cited by this paper
• Conditional Symmetry Breaking

  2005cited by this paper
• Lifted First-Order Probabilistic Inference

  2005cited by this paper
• First-order probabilistic inference

  2003cited by this paper
• The product replacement algorithm is polynomial

  2000cited by this paper
• In Advances in Neural Information Processing Systems

  1996cited by this paper
• Context-Specific Independence in Bayesian Networks

  1996cited by this paper
• Principles and Practice of Constraint Programming

  1995cited by this paper
• Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence Lifted Probabilistic Inference by First-Order Knowledge Compilation

  year unknowncited by this paper

• Symmetry-Based Representations for Artificial and Biological General Intelligence

  2022cites this paper
• Contrastive Learning in Neural Tensor Networks using Asymmetric Examples

  2021cites this paper
• On Lifted Inference Using Neural Embeddings

  2019cites this paper
• Fast Markov chain Monte Carlo algorithms via Lie groups

  2019cites this paper
• State-Space Abstractions for Probabilistic Inference: A Systematic Review

  2018cites this paper
• Block-Value Symmetries in Probabilistic Graphical Models

  2018cites this paper
• Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go?

  2018cites this paper
• Learning Embeddings for Approximate Lifted Inference in MLNs

  2018cites this paper
• Representing and learning relations and properties under uncertainty

  2018cites this paper
• Coarse-to-Fine Lifted MAP Inference in Computer Vision

  2017cites this paper
• Conditional Term Equivalent Symmetry Breaking for SAT

  2017cites this paper
• Non-Count Symmetries in Boolean & Multi-Valued Prob. Graphical Models

  2017cites this paper
• Lifting Techniques for Sequential Decision Making and Probabilistic Inference (Extended Abstract)

  2016cites this paper