Automorphism Groups of Graphical Models and Lifted Variational Inference

By Hung Hai Bui, Tuyen N. Huynh, Sebastian Riedel. 2012

74 citations recorded by the source corpus.

Using the theory of group action, we first introduce the concept of the automorphism group of an exponential family or a graphical model, thus formalizing the general notion of symmetry of a probabilistic model. This automorphism group provides a precise mathematical framework for lifted inference in the general exponential family. Its group action partitions the set of random variables and feature functions into equivalent classes (called orbits) having identical marginals and expectations. Then the inference problem is effectively reduced to that of computing marginals or expectations for each class, thus avoiding the need to deal with each individual variable or feature. We demonstrate the usefulness of this general framework in lifting two classes of variational approximation for MAP inference: local LP relaxation and local LP relaxation with cycle constraints; the latter yields the first lifted inference that operate on a bound tighter than local constraints. Initial experimental results demonstrate that lifted MAP inference with cycle constraints achieved the state of the art performance, obtaining much better objective function values than local approximation while remaining relatively efficient.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Equivariance Through Parameter-Sharing (2017, methodology): “In particular, many probabilistic inference techniques have been extended to graphical models with known symmetry groups (Raedt et al., 2016; Kersting et al., 2009; Bui et al., 2012; Niepert, 2012).”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, methodology): “However, this comes at a computational price and therefore it is often needed to restrict the expressivity of the model by only using model structures that are known to be tractable [221, 117] or to approximate the inference [220, 119, 24].”
Representation Learning for Dynamic Graphs: A Survey (2019, background): “(2009); Bui et al. (2013)). In contrast, inference with encoder-decoder models usually scales to large datasets and although the operators used for inference are in some cases questionable, end-to-end learning allows the weights of the operators to be adjusted to yield the best predictions possible ”